728x90
2624번: 동전 바꿔주기
명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을
www.acmicpc.net
분석
- dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수
- dp[money] += dp[money - coin * cnt]
(money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수)
풀이
"""
입력으로 지폐의 금액 T
동전의 가지 수 k
각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k)
지폐를 동전으로 교환하는 방법의 가지 수
"""
t=int(input()) # 지폐금액
k=int(input()) # 동전가지수
coins=[(0,0)]
for i in range(k):
pi,ni=map(int, input().split())
coins.append((pi,ni))
# dp[i][j] : i번째 동전까지 사용해서 j원을 만들 수 있는 경우의 수
dp = [[0 for _ in range(t+1)] for _ in range(k+1)]
dp[0][0] = 1 # 0원은 아무 동전도 사용하지 않는 경우가 하나 있으므로 1로 초기화
for i in range(1, k+1): # 각 동전마다
val, cnt = coins[i]
for j in range(t+1): # T원까지
dp[i][j] = dp[i-1][j]
for v in range(1, cnt+1):# 동전 갯수만큼 반복
if j-v*val >= 0:
dp[i][j] += dp[i-1][j-v*val]
else:
break
print(dp[k][t])
728x90