문제
접근
DP 문제이다.
n의 크기만큼, 그리고 화폐 종류만큼 미리 배열을 할당해준다.
DP(x,y) 는 x번째 화폐까지 사용하여 y원을 만들 수 있는 경우의 수라하자.
예제처럼 화폐 종류가 1,2,5가 있을 때, DP(2, 10)은 1,2원을 사용하여 10원을 만들 수 있는 경우의 수이다.
이제 그럼 DP를 어떻게 계산해 나갈지 생각해보자.
우선 DP(2, 1) 처럼 1,2 원을 사용하지만 만들고자하는 금액이 화페단위보다 작은 경우가 있다.
이런 경우는 DP(1, 1)과 똑같은 결과를 가진다.
이렇지 않은 경우에는 우선 x-1 번째 까지 사용했을 때의 경우의 수, DP(x-1,y)
money(x)를 한개 사용하고의 경우의 수, 즉 DP(x, y-money(x)) 의 합이 된다.
즉, DP(x,y) = DP(x-1, y) + DP(x, y-money(x)) 이다.
이해가 안되면 작은 범위라도 표로 그려가면서 따라간다면 쉬울 것이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
def solution(n, money):
dp = [[0] *(n+1) for _ in range(len(money))]
dp[0][0] = 1
for i in range(money[0], n+1, money[0]):
dp[0][i] = 1
for j in range(n+1):
for i in range(1, len(money)):
if j >= money[i]:
dp[i][j] = (dp[i-1][j] + dp[i][j - money[i]]) % 1000000007
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]