[2624] 동전 바꿔주기

문제

https://www.acmicpc.net/problem/2624

출력

첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.

풀이

dp문제라는 것은 파악했지만 풀이를 하지 못했다.

T에서 내림차순으로 구해주는 이유는 같은 코인의 영향을 주지 않기 위해서다.

예를들어 금액이 1이고, 개수가 2인 경우를 구해준다음 배열의 상태가 [1, 1, 1, 0, 0, 0, 0] 일 때 코인의 금액은 2이고, 개수는 10이라 해보자

만약 1부터 오름차순으로 누적해서 구해준다면 2까지는 [1, 1, 2, 0, 0, 0, 0]일 것이다.

이대로 6까지만 해준다면 6은 1 + 2 = 3가지의 경우가 나온다. 그러나 정답은 (1+1+2+2, 2+2+2) 총 두 가지의 경우 밖에 나오지 않는다.

dp[2]의 값에는 이미 금액이 같은 2인 코인이 들어있었기 때문에 다른 경우라고 볼 수 없지만 오름차순으로 구하는 과정에서 이 경우를 포함해서 구하게 된다. 따라서 내림차순으로 값을 누적하여 건들지 못하게 해야한다

import sys

T = int(sys.stdin.readline())
k = int(sys.stdin.readline())
coins = []
dp = [1] + [0] * T

for _ in range(k):
    cost, count = map(int, sys.stdin.readline().split())
    coins.append((cost, count))

for cost, count in coins:
    for cur_cost in range(T, 0, -1):
        for i in range(1, count + 1):
            if cur_cost >= cost * i:
                dp[cur_cost] += dp[cur_cost - (cost * i)]

print(dp[T])