Project Euler #31 - 동전 조합 경우의 수

프로젝트 오일러 31번
1, 2, 5, 10, 20, 50, 100, 200페니짜리 동전으로 200페니를 만들 수 있는 가지수는?

1페니짜리 200개,
1*198 + 2*1
...
200*1
꽤 많은 가짓수가 존재하는 머리 아픈 문제지만 터무니없이(?) 짧은 코드로 답이 나온다.

c = [1,2,5,10,20,50,100,200]
s = {i:0 for i in range(1,201)}
for i in c:
    s[i] += 1
    for j in range(i+1,201):
        s[j] += s[j-i]
        
print s[200]

좀 더 간단한 문제로.. 1페니와 2페니 동전만으로 1, 2, 3, ..., 10 페니를 만드는 가짓수를 각각 구해보자.
1 <= 당연히 한가지
2 <= 2: 1+1, 2
3 <= 2: 1+1+1, 1+2
4 <= 3: 1+1+1+1, 1+1+2, 2+2
5 <= 3: ...
(귀찮아서 생략)
n 페니를 만드는 방법
 = (1페니만으로 만드는 방법) + (2페니를 사용하는 방법)
 = 1 + (어떻게든 n-2페니를 만들고 2페니짜리를 하나 더 사용하는 방법)

다시 한 번 반복..
1, 2 페니만 사용해서 n 페니를 만드는 가지수를 f(n)이라고 하면,
f(1) = 1
f(2) = 2
f(3) = 1 + f(1) = 2
f(4) = 1 + f(2) = 3
f(5) = 1 + f(3) = 3
...

이번에는 1, 2, 5페니만 사용해서 n페니를 만드는 가지수를 g(n)이라고 하면,
n페니를 만드는 방법
 = (1,2페니만드로 만드는 방법) + (어떻게든 n-5페니를 만들고 5페니짜리 하나를 얹는 방법)
 = f(n) + g(n-5)

이걸 5, 10, 20, ... 200페니 동전까지 적용하면 위의 코드가 된다.
brilliant!




덧, s를 dictionary로 정의하는 대신 list로 해도 된다. 여기서는 s = [0]*201로 정의해도 답이 똑같이 나온다.


덧2, 처음에 짰던 코드는

left = 200
for p200 in range(1):
    left -= p200*200
    for p100 in range(2):
        left -= p100*100
        ...

이런 식이었다. 답도 금방 나오고 이해하기도 쉽고 (그치만 코드는 매우 지저분....).. 그런데 저장하기 전에 파이썬(정확히 말하면 내가 쓰는 IDE - Enthought Canopy)가 죽어버렸다.

포럼에서 봤던 위 스타일의 코드가 생각나서 다시 작성할 때는 따라해 봤다.