[Project Euler] Problem 31

원문: Problem 31

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를 만들 수 있는 서로 다른 방법은 몇 개인가?

Python 1

가장 단순하지만 무식한 방법이다. 그만큼 시간도 오래 걸린다. 대략 20분 이상이 소요됐다.

>>> n = 1 # £2 한 개 사용
>>> for p1 in range(201):
...     for p2 in range(101):
...             for p5 in range(41):
...                     for p10 in range(21):
...                             for p20 in range(11):
...                                     for p50 in range(5):
...                                             for p100 in range(3):
...                                                     if (p1 + 2 * p2 + 5 * p5 + 10 * p10 + 20 * p20 + 50 * p50 + 100 * p100) == 200:
...                                                             n += 1
...                                                               
>>> print(n)

접기

Python 2

수학을 조금 이용해서 제한 조건을 거는 방법이다. 20초 정도 걸렸다.

>>> n = 1
>>> for p1 in range(201):
...     for p2 in range(101):
...             if (p1 + 2 * p2) % 5 != 0: # 5펜스 단위가 되어야 5p와 짝을 이룰 수 있음
...                     continue
...             for p5 in range(41):
...                     for p10 in range(21):
...                             for p20 in range(11):
...                                     if (p1 + 2 * p2 + 5 * p5 + 10 * p10 + 20 * p20) % 50 != 0: # 마찬가지로 50펜스 단위가 되어야 50p와 짝을 이룰 수 있음
...                                             continue
...                                     for p50 in range(5):
...                                             for p100 in range(3):
...                                                     if (p1 + 2 * p2 + 5 * p5 + 10 * p10 + 20 * p20 + 50 * p50 + 100 * p100) == 200:
...                                                             n += 1
...                                                               
>>> print(n)

접기

Python 3

문제를 풀고나서 포럼에 있는 내용을 참고해서 얻은 아이디어를 이용해서 재귀로 구현하였다. 실행 즉시 결과가 나온다.

>>> n = 0
>>> coins = [200, 100, 50, 20, 10, 5, 2, 1]
>>> def func(remain, remain_coins):
...     global n
...     if remain_coins[0] == 1: # 1펜스만 남게 되면 1펜스로만 계산해야 함
...             n += 1
...             return
...     for k in range(remain // remain_coins[0] + 1):
...             if remain - remain_coins[0] * k == 0: # 현재 동전으로 모두 계산이 끝남
...                     n += 1
...                     return
...             func(remain - remain_coins[0] * k, remain_coins[1:])
... 
>>> func(200, coins)
>>> print(n)

접기

이 외에도 DP 솔루션과 같은 좀 더 고급적인 방법을 이용해서 풀은 사람들을 포럼에서 볼 수가 있다.