프로젝트 오일러 31번

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?

---

영국에는 다음과 같이 8가지 종류의 동전이 있다.

1펜스, 2펜스, 5펜스, 10펜스, 20펜스, 50펜스, 1파운드 (=100펜스), 2파운드(=200펜스)

이 동전들을 이용하여 2파운드를 지불하는 방법은 다음과 같은 것이 가능하다.

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

이와 같이 2파운드를 지불하는 서로 다른 방법은 몇 가지가 가능할까?

언제나 그렇듯이 이 문제는 원시적으로 접근하는 것이 가능하다.

단위가 큰 금액부터 얼마나 사용할 것인지 결정한 후에, 나머지 금액을 어떻게 지불할 것이지 생각하면 된다.

일명 노가다가 된다. 실제로 고등학교 수학문제에서 이런 식으로 경우의 수를 세는 문제가 출제되기도 한다.

그렇지만 동전이나 지폐의 종류가 더 많아지고, 지불해야할 금액이 커지면 커질수록 이런식으로 접근하는 방법은 그야말로 노가다가 된다.

따라서 단순화한 문제를 풀면서 어떤 식으로 이 문제에 접근해야 하는지 살펴보자.

편의상 1원, 2원, 5원 짜리 동전 세 가지를 가지고 5원을 지불하는 방법을 생각해 보자.

일단 이 문제를 손으로 풀어보면

(1, 1, 1, 1, 1),  (1, 1, 1, 2),  (1, 2, 2),  (5)

의 4가지의 방법이 가능한 것을 알 수 있다.

 이제 다른 식으로 접근해 보자.

 

<표 1>

0원	1원	2원	3원	4원	5원
1	1	1	1	1	1

 

위의 표는 각 금액을 1원 짜리 동전을 사용하여 지불하는 경우의 수를 나타낸다.

관심있게 봐야 하는 것은 0원을 1원 짜리 동전만을 사용하여 지불하는 경우의 수는 지불하지 않는 방법 1가지가 있다고 생각해야 한다는 것이다. (이렇게 생각해야만 차후 계산이 편해진다.)

이제 2원 짜리 동전을 사용하는 경우를 생각해 보자. 2원 짜리 동전을 사용하여 지불할 수 있는 금액은 2원 이상이 되기 때문에 2원 이상의 경우만 생각하면 된다.

 

 <표 2>

0원	1원	2원	3원	4원	5원
1	1	2	2	3	3

 

2원을 지불하기 위해서 2원 짜리 동전을 하나 사용했다면 더 지불해야 하는 금액은 0원이다. 0원을 지불하는 방법은 1가지(<표 1>에서 관심있게 봤던 부분) 이기 때문에 2원을 1원이나 2원 짜리를 이용하여 지불하는 방법은 1+1 (1원만 사용하여 지불하는 경우의 수+2원 짜리를 사용하여 지불하는 경우의 수) 이 되어 2 가지가 된다. (이 두 가지는 (1, 1), (2)가 된다.) 

또한 3원을 지불하기 위해서 2원 짜리 동전을 하나 사용했다면 더 지불해야 하는 금액은 1원이다. <표 1>에서 1원을 지불하는 방법의 수는 1이기 때문에 이 경우도 1+1=2 가지가 되는 것을 알 수 있다. (이 두 가지는 (1, 1, 1), (1, 2)가 된다.)

4원을 지불하기 위해서 2원 짜리 동전을 하나 사용했다면 더 지불해야 하는 금액은 2원이다. 2원을 지불하는 방법은 <표 2>에서 2가지를 이미 구해 놨다. 따라서 1+2=3가지가 된다. (이 세 가지는 (1, 1, 1, 1), (1, 1, 2), (2, 2)가 된다.)

5원을 지불하기 위해서 2원 짜리 동전을 하나 사용했다면 더 지불해야 하는 금액은 3원이다. 3원을 지불하는 방법은 <표 2>에서 2가지를 이미 구해 놨다. 따라서 1+2=3가지가 된다. (이 세 가지는 (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2)가 된다.)

 

 <표 3>

0원	1원	2원	3원	4원	5원
1	1	2	2	3	4

 

5원을 지불하기 위해서 5원 짜리 동전을 하나 사용했다면 더 지불해야 하는 금액은 0원이다. 0원을 지불하는 방법은 1가지 이므로 <표 3>에서 구한 경우의 수 3에 1을 더해주면 된다. 1+3=4가지가 된다. (이 네 가지는 (1, 1, 1, 1, 1), (1, 1, 1, 2), (1, 2, 2), (5)가 된다.)

 

결국 1원, 2원, 5원 짜리 동전을 사용하여 5원을 지불하는 방법의 수는 4가지가 된다.

31번 문제는 8개 종류의 금액으로 200파운드를 지불하는 방법의 수를 구하는 문제다.

위와 같은 방법으로 접근하면 파이썬의 경우 10행 내외의 코딩으로 해결이 가능하다.