BOJ 다이나믹 프로그래밍 알고리즘 풀이
2293번 - 동전 1
해당 문제는 n가지 종류의 동전을 이용해서 주어진 금액을 만들 수 있는 경우의 수를 구하면 됩니다.
동전별로 최소 금액부터 구해야하는 최대 금액을 만들 때까지의 경우의 수를 구하면 됩니다.
1원, 4원, 5원의 3가지 동전이 주어졌을 때, 10원을 만들 수 있는 경우의 수를 생각해봅니다. 먼저 첫 번째 동전만을 이용해서 구할 수 있는 경우의 수를 생각해봅니다.
| - | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
첫 번째 동전인 1원만으로는 모든 금액에 대해서 1가지의 경우의 수 밖에 가질 수 없습니다. 두 번째 동전인 4원일 때의 경우의 수를 생각해봅니다. 첫 번째 동전일 때의 경우의 수에 누적해서 계산합니다.
| - | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 1+1 | 1+1 | 1+1 | 1+1 | 1+2 | 1+2 | 1+2 |
금액 1, 2, 3원은 현재 주어진 동전 중 1원으로만 경우의 수를 구할 수 있기 때문에 1가지입니다.
구해야 하는 금액이 4원일 때, 경우의 수가 1원일 때의 경우의 수(1가지=1+1+1+1)에 4원으로 구할 수 있는 경우의 수(1가지=4)로 총 2가지입니다. 그리고 5, 6, 7일 때도 마찬가지로 1원일 때 경우의 수 1가지 4원일 때 경우의 수 1가지로 2가지가 됩니다.
8원일 때에는 1원일 때 경우의 수(1가지=1+1+1+1+1+1+1+1)와 4원으로 구할 수 있는 경우의 수(1가지=4+4) 1, 4원을 이용할 때 경우의 수(1가지=1+1+1+1+4)로 총 3가지입니다. 나머지 9, 10원도 동일하게 3가지 경우의 수를 구할 수 있습니다.
다음으로 마지막 동전인 5일 때의 경우의 수를 생각해봅니다.
| - | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 |
| 5 | 1 | 1 | 1 | 2 | 2+1 | 2+1 | 2+1 | 3+1 | 3+2 | 3+3 |
1, 2, 3, 4원은 현재 주어진 5원으로는 경우의 수를 구할 수 없기 때문에 기존의 경우의 수를 유지합니다. 구해야 하는 금액이 5원일 때, 4원일 때 구했던 경우의 수(2가지=1+1+1+1, 4)에 5원일 때의 경우의 수(1가지=5)로 3가지가 됩니다.
6원일 때는 기존에 1, 4원을 이용해서 6원을 만들 수 있는 경우의 수(2가지)에 6원-5원=1원일 때, 동전 5원에서 금액 1원을 구할 때의 경우의 수는 1가지이기 때문에 경우의 수는 3가지가 됩니다. 7, 8, 9, 10원도 동일하게 이전 동전으로 구했던 경우의 수에 현재 선택된 동전에서 남은 금액을 만들기 위한 경우의 수를 더해주면 됩니다. 즉, 선택된 동전을 이용해 현재 금액을 만들기 위한 경우의 수는(dp[k])는 이전 동전들을 이용해서 구한 선택된 금액의 경우의 수(dp[k])에 선택된 금액에서 동전을 제외했을 때, 구할 수 있는 경우의 수를 더하면 됩니다.
위의 내용을 토대로 점화식을 만들게 되면 다음과 같습니다.
해당 금액을 만들 수 있는 경우의 수 = 이전 동전들로 만든 해당 금액의 경우의 수 + (금액 - 동전)의 금액을 만들 수 있는 경우의 수
dp[k] = dp[k] + dp[k-coin[n]] (dp=경우의 수, k=금액, coin[n]=선택된 동전)
상세 코드 구현은 아래 코드를 참고해주세요.