Project Euler 31

Question: 

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

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

It is possible to make £2 in the following way:

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

How many different ways can £2 be made using any number of coins?

문제:

영국의 화폐는 파운드, £, 펜스, p로 구성되는데 일반적으로 8개의 동전이 있다.

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

다음과 같은 방법으로 £2 를 만들 수 있다.

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

£2 를 만드는 모든 방법의 수는 몇 가지나 될까?

Solution:

출처: https://www.xarg.org/puzzle/project-euler/problem-31/

먼저, 1p, 2p, 그리고 5p를 가지고 5p 를 만드는 가짓수를 생각해보자.

1. 1p 만을 쓰는 방법.

총합	1p만을 써서 만드는 경우의 수
0	1
1	1
2	1
3	1
4	1
5	1

이 때 총합 0을 넣은 이유는 후에 계산과정을 보다 간편히 보기 위해서이다.

2. + 2p 를 쓰는 방법

총합	2p를 더 써서 만드는 경우의 수
0	1
1	1
2	2
3	2
4	3
5	3

여기서 눈 여겨 볼 점은, 2p를 쓸 때에, 총합이 2보다 적은 경우의 수는 변함이 없다는 점이다.

3. + 5p 를 쓰는 방법

총합	5p를 더 써서 만드는 경우의 수
0	1
1	1
2	2
3	2
4	3
5	4

마찬가지로, 총합이 5p보다 작은 경우의 수는 더이상 변함이 없다.

따라서, 이 리스트에서 마지막 숫자가 우리가 구하고 싶은 경우의 수다.

위처럼, 가장 작은 동전부터 채워나가기 시작해서, 그다음 큰 동전으로 채워나가는 방식을 사용하자.

import time

total = 200

currency = [1, 2, 5, 10, 20, 50, 100, 200]
coins = [1] + [0] * total # 총합이 0p 일때 + 마지막 항이 원하는 합계

start = time.time()
for i in currency:
    for j in range(i, total+1):
        coins[j] += coins[j-i] # 가장 작은 동전부터 채워넣는다. 
                               # j-i 은 j동전보다 작은 경우의 수를 제외시킨다.

print(coins[-1])
print('Found in ...{:.2f}'.format(time.time() - start))

매우짧은 시간이 걸렸다!

효율적인 코딩을 하기 위해 조금의 리서치가 필요했다.

73682