[오일러프로젝트] 31번문제

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)

이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?



brute-force로 풀었는데 시간이 상당히 걸린다.
문제 풀이 후 좀 더 찾아보니 전형적인 Dynamic Programming 알고리즘의 문제라고 한다.

아래의 내 코드가 약 1분 정도가 소요되는데
DP 방식으로 구현된 이 코드

http://blog.dreamshire.com/2009/03/31/project-euler-problem-31-solution/

는... 20초안에 결과가 나온다. 코드를 봐도 어떻게 저렇게 풀리는지 이해가 잘 되지 않는다..흠.. 일단 점화식(?)을 찾는 것이 관건인 것 같은데... 그게 잘 안나오네..

 

Python

	i=0
	a=[0]*6
	a[1]=1
	for n in range(2, 5):
	a[n]=a[n-1]+n
	print (a[4])
	"""
	n=0
	for p1 in range(0, 201):
	for p2 in range(0, 101):
	if(p1 + 2*p2) % 5 != 0:
	continue
	for p5 in range(0, 41):
	for p10 in range(0, 21):
	for p20 in range(0, 11):
	if(p1+2*p2+5*p5+10*p10+20*p20) %50 != 0:
	continue
	for p50 in range(0, 5):
	for p100 in range(0, 3):
	for p200 in range(0, 2):
	s=(p1 + 2*p2 + 5*p5 + 10*p10 + 20*p20 + 50*p50 + 100*p100 + 200*p200)
	if s == 200:
	n+=1
	print (n)

view raw 31.py hosted with ❤ by GitHub

> 위 주석부분은 가장 간단한 DP코드인데.. 저건 이해가 되더만...그래도..
Ruby

	n=0
	(0..200).each do |p1|
	(0..100).each do |p2|
	if (p1 + 2*p2) % 5 != 0
	next
	end
	(0..40).each do |p5|
	(0..20).each do |p10|
	(0..10).each do |p20|
	if (p1 + 2*p2 + 5*p5 + 10*p10 + 20*p20) % 50 != 0
	next
	end
	(0..4).each do |p50|
	(0..2).each do |p100|
	(0..1).each do |p200|
	if (p1 + 2*p2 + 5*p5 + 10*p10 + 20*p20 + 50*p50 + 100*p100 + 200*p200) == 200
	n+=1
	end
	end
	end
	end
	end
	end
	end
	end
	end
	puts n

view raw 31.rb hosted with ❤ by GitHub

Perl

	my $n=0;
	foreach my $p1 ((0..200)) {
	foreach my $p2 ((0..100)) {
	if (($p1+2*$p2) % 5 != 0) {
	next;
	}
	foreach my $p5 ((0..40)) {
	foreach my $p10 ((0..20)) {
	foreach my $p20 ((0..10)) {
	if (($p1+2*$p2+5*$p5+10*$p10+20*$p20) % 50 != 0) {
	next;
	}
	foreach my $p50 ((0..4)) {
	foreach my $p100 ((0..2)) {
	foreach my $p200 ((0..1)) {
	if (($p1+2*$p2+5*$p5+10*$p10+20*$p20+50*$p50+100*$p100+200*$p200) == 200) {
	$n+=1;
	}
	}
	}
	}
	}
	}
	}
	}
	}
	print "$n";

view raw 31.pl hosted with ❤ by GitHub

알고리즘의 힘을 느낀 문제..