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

https://euler.synap.co.kr/problem=31

접근

이 문제는 전형적인 동적 프로그래밍 방식의 문제이다. 이 문제를 실제 조합 가능한 방법을 하나 하나 찾아서 세어 보면 정말이지 끝도 없는 수렁에 빠지게 된다. 이 글의 이전 버전에서는 무식한 방법에서 시작하여 메모이제이션을 통해 성능을 조금 개선하였고, 그 마저도 여의치 않아서 동적 프로그래밍을 적용하는 단계로 발전시켰는데, 굳이 도움되지 않을 무식한 방법들을 소개할 필요는 없는 것 같아서 제외했다.

계단을 오르는 예

이 문제보다 좀 더 간단한 다른 버전의 문제를 우선 생각해보자. 5칸짜리 짧은 계단이 있다. 계단을 오를 때에는 한 칸만 오르거나 한 번에 두 칸을 오를 수 있다면 이 5칸짜리 짧은 계단을 오르는 방법의 수는 몇 가지일까?

사실 이 문제는 피보나치 수열하고 똑같은 문제이다. 이렇게 생각해보자.

1. 당신은 어느 시점에 5칸의 계단을 모두 올랐다. 당신은 이 직전 순간, 어느 계단에 서 있었을까?
2. 아마 한 번에 하나 혹은 두 개의 계단을 오를 수 있으니, 3번째 계단 혹은 4번째 계단에 서 있었을 것이다.
3. 따라서 다섯 번째 계단에 오르는 방법의 가지 수는 3번째 계단에 오르는 방법의 가지 수와 4번째 계단에 오르는 방법의 가지수를 더한 것과 같을 것이다.

말을 바꾸면 1p, 2p 동전으로 5p를 만드는 방법의 가지 수와 같은 셈이다. 계단을 좀 많이 오른다고 생각한다면, 1p, 2p 동전만으로 200p를 만드는 방법의 가지 수를 구하는 문제와 동일할 것이다.

따라서 동전을 조합하는 경우의 수도 비슷하게 점화식으로 만들 수 있다. m을 만드는 방법의 가짓수를 F(m) 이라 하고, 동전의 액면가를 c₁, c₂, c₃, …, c_k 라 한다면, 아래와 같이 점화식을 정리할 수 있다.

\begin{array}{ll}
F(m) &= F(m-c_1) + F(m - c_2) + \dots + F(m - c_k) \\
&= \sum_{i=1}^{k}F(m - c_i) \\
F(c_1) &= 1 \\
F(c_2) &= 1 \\
\vdots \\
F(c_k) &= 1
\end{array}

당연히 이 점화식을 재귀로 구현하면 아주 느릴 것이다. 따라서 다음과 같이 크기가 200인 배열을 만들어 두고 앞에서부터 계산한다.

%%time

coins = (1, 2, 5, 10, 50, 100)
ways = [1] + [0] * 200
for coin in coins:
  for i in range(coin, 200):
    ways[i] += ways[i - coin]

print(ways[-1])