프로젝트 오일러 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파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?

-------------------------------------------------------------
target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [1] + [0]*target

for coin in coins:
    for i in range(coin, target+1):
        ways[i] += ways[i-coin]

print ways[-1]
-----------------------------------------------------------------
이런 알고리즘 사용하는 게 아직 쉽지 않다.. 나는 for문 여러개 만들어서 했지만 답은 dp 알고리즘이 더 간단하다. 아직 읽지 못한 알고리즘 책을 읽어야겠다..