[백준] 2624 동전 바꿔주기

문제

• k가지 동전과 동전의 개수가 주어질 때, T원의 지폐를 동전으로 교환하는 방법의 수 구하기
• 1 <= T <= 10000
• 1 <= k <= 100
• 1 <= 동전 개수 <= 1000

 

풀이

• 최대 T원까지 동전을 개수만큼 교환하는 방법을 각각 구해준다.
• 예제로 예를 들면,
  • coins = [ (5, 3), (10, 2), (1, 5) ]
    • (5, 3) => dp[15], dp[10], dp[5] 가 1이 됨
    • (10, 2) => dp[20], dp[15], dp[10] 2가 됨
      • dp[20]  += dp[20 - 10]
      • dp[20] += dp[20 - 20]
    • (1, 5)
      • dp[20] += dp[20 - 5]

 

import sys
input = sys.stdin.readline

T = int(input())
k = int(input())
coins = []
for _ in range(k) :
    p, n = map(int, input().split())
    coins.append((p, n))

dp = [0] * (T+1)
dp[0] = 1

for coin, cnt in coins :
    for sum in range(T, 0, -1) :        # T원에서 0원이 될 때까지 동전 하나씩 교환
        for i in range(1, cnt+1) :      # 현재 동전 개수만큼 교환
            if sum - coin * i >= 0 :
                dp[sum] += dp[sum - coin * i]

print(dp[T])

 

References

• 백준 DP