[Programmers/Python] Dynamic programming - 거스름돈

Programmers - 거스름돈

---

문제

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

• 1원을 5개 사용해서 거슬러 준다.
• 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
• 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
• 5원을 1개 사용해서 거슬러 준다.

거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

입출력 예

n	money	result
5	[1,2,5]	4

입출력 예 설명

• 입출력 예 #1
  문제의 예시와 같습니다.

---

풀이

설계

도저히 아이디어가 안 떠올라서 힌트를 검색해보고 DP라는 것을 확인한 다음 다시 설계를 해 보았다. 내가 이해한 DP의 핵심은 문제를 작은 단위의 문제로 쪼개고, 각 문제의 정답을 기억하기 위한 리스트를 만들어 해당 리스트의 값을 활용함으로써 시간복잡도 면에서 이득을 보는 것이었다.

DP 구현 자체는 어렵지 않았는데, 문제는 문제를 '쪼개는' 부분에 있었다. n에 대한 경우의 수와 n-1에 대한 경우의 수에 어떤 관계가 있는지를 파악하는 것이 상당히 어려웠고, 심지어 힌트를 보았음에도 이해하는 데 상당한 시간이 걸렸다.

개인적으로는 동전의 종류에 '1'이 포함되는 순간 문제를 이해하기가 더 어려워진다는 생각이 들어 1을 제외한 동전으로 내용을 정리해 본다.

우선 기본적인 전제는 다음과 같다.

• memoization[0]은 1이다. 어떤 동전을 사용하든 0을 만드는 경우의 수는 1가지뿐이므로.
• n을 만드는 경우의 수는 각 동전으로 n을 만드는 경우의 수를 모두 더한 것이다.
• coin으로 n을 만드는 경우의 수는 n-coin을 만드는 경우의 수와 같다.

사실 이 전제를 이해하는 것이 가장 어려웠는데, 예를 통해서 이해해보자.

2원과 4원 동전으로 8원을 만드는 경우의 수를 구해보자. 가장 먼저 2원짜리 동전으로 1원부터 8원까지의 금액을 만드는 경우의 수를 구해보면, 어차피 2원짜리 동전만 사용하는 방법밖에 없으므로 2, 4, 6, 8원을 만드는 경우의 수는 모두 1이 될 것이다.

[memoization_1]

0	1	2	3	4	5	6	7	8
1	0	1	0	1	0	1	0	1

여기에 이번에는 4원짜리를 이용해 각각의 n을 만드는 경우의 수를 더해보자. 이때 4 미만의 수는 어차피 4원짜리로 만들 수 없으므로 4부터 n까지만 확인한다.

[memoization_2]

0	1	2	3	4	5	6	7	8
1	0	1	0	2	0	2	0	3

두 표의 값을 비교해 보면 4원짜리 동전을 이용해 n을 만드는 경우의 수 memoization_2[n]은 memoization_1[n] + memoization_2[(n-4)]가 됨을 알수 있다. 즉, 동전의 종류별로 순차적으로 경우의 수를 더할 때, 각 경우의 수 memoization[n]은 memoization[n] + memoization[n-coin]이 되는 것이다.

8을 예로 들어 보자. 현재 반복문에서 coin이 4일 때 memoization[8]을 구하는 코드는 memoization[8] + memoization[4]가 될 것이다. 그런데 2와 4로 4를 만드는 방법은 두 가지이다.

• 2+2
• 4

이 각각의 경우에 현재 coin 단위인 4를 붙이면 각각 2+2+4 / 4+4가 되며, 결국 경우의 수는 2가지로 동일하다. 따라서 4를 사용하지 않고 8을 만드는 경우의 수(즉, 2만으로 8을 만드는 경우의 수 1)에 4를 만드는 경우의 수를 더하면 2와 4로 8을 만드는 경우의 수가 되는 것이다.

---

이해가 어려운 만큼 설명하는 것도 쉽지 않은 문제이다. 여하튼 여기까지 이해하고 나면 코드 자체는 단순하게 구현된다.

코드

def solution(n, money):
    memoization = [0] * (n + 1)  # 각 경우의 수를 기억하기 위한 리스트
    memoization[0] = 1  # 0을 만드는 경우의 수 설정
    
    for coin in money:
        for i in range(coin, n+1):
            memoization[i] += memoization[i - coin]
    return memoization[n] % 1000000007