백준 2624번

동전 바꿔주기

시간 제한 : 1초 메모리 제한 : 128 MB

문제

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5 입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.

입력

첫째 줄에는 지폐의 금액 T(0＜T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0＜k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi ≤ T)와 개수 ni(0＜ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.

출력

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

해설

이 문제는 주어진 동전들로 특정 금액을 만들 수 있는 방법의 수를 찾는 동적 프로그래밍 문제입니다.

주요 아이디어는 다음과 같습니다:

dp 배열을 사용하여 각 금액을 만들 수 있는 방법의 수를 저장합니다. 각 동전과 그 동전의 개수를 사용하여 dp 배열을 업데이트합니다. 다음과 같은 방법으로 문제를 접근합니다:

1. 입력: 지폐의 금액 t, 동전의 종류 수 k, 그리고 각 동전의 금액 p와 개수 n을 입력받습니다.
2. dp 배열 초기화: 길이가 t+1인 dp 배열을 생성하고, dp[0]을 1로 설정합니다. dp[0] = 1인 이유는 0원을 만드는 방법은 하나(동전을 사용하지 않는 방법)이기 때문입니다.
3. 동전 별 계산: 각 동전과 그 동전의 개수에 대하여, t부터 p까지 역순으로 접근하면서 dp 배열을 업데이트합니다. 이때, 각 동전의 금액과 개수를 사용하여 현재 금액 i를 만들 수 있는 방법의 수를 계산하고 dp 배열에 추가합니다.
4. 결과 출력: dp[t]에는 금액 t를 만들 수 있는 방법의 수가 저장되어 있으므로, 이 값을 출력합니다. 이 방법을 사용하면 주어진 동전들로 특정 금액을 만들 수 있는 방법의 수를 효율적으로 계산할 수 있습니다.

t = int(input())
k = int(input())  

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

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

for p, n in coins:
    for i in range(t, p-1, -1):
        for j in range(1, n+1):
            if i < j*p:
                break
            dp[i] += dp[i-j*p]

print(dp[t])