2624. 동전 바꿔주기 (Python)

2624번: 동전 바꿔주기

 

풀이

 1차원 dp를 사용하는데 dp 배열의 의미는 다음과 같다.

dp[n] : 금액 n의 동전 교환 방법 경우의 수 

 모든 dp 배열의 값은 0으로 초기화 되지만 dp[0]은 아무 동전도 사용하지 않는 경우 하나가 존재한다고 가정하여 dp[0]은 1로 초기화한다.

 

 경우의 수를 구하기 위한 점화식은 다음과 같다.

dp[money] += dp[money - coin * cnt]
(money는 구하기 위한 금액, coin은 현재 사용하는 동전의 금액, cnt는 사용하는 동전의 개수)

 경우의 수를 구하기 위해서 금액 T부터 0까지 내려가며 구한다.

 

 문제의 예제를 생각해보자. 20원을 만들어야 하고 먼저 10원짜리 동전을 사용한다고 가정해보자. 10원 동전은 총 2개가 있다. 먼저 dp[20]은 dp[20 - 10 * 1]과 dp[20 - 10 * 2]의 값을 더해서 구할 수 있다. 즉, 20원은 10원의 경우의 수에 10원짜리 동전 1개를 사용하여 만들 수 있고 0원의 경우의 수에 10원짜리 동전 2개를 사용하여 만들 수 있다는 것을 의미한다. 

 

 위와 같은 방법으로 모든 동전에 대하여 경우의 수를 더해주면 최종적으로 T 금액을 만들 수 있는 경우의 수를 구할 수 있다.

 

코드

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    T = int(input()) # 지폐의 금액
    K = int(input()) # 동전의 가지 수 
    coins = [] # 동전 정보
    dp = [0] * (T+1) # dp[n] : n 금액에 대한 동전 교환 방법의 가지 수 
    dp[0] = 1 # 0원은 아무 동전도 사용하지 않는 경우가 하나 있으므로 1로 초기화 

    for _ in range(K):
        p, n = map(int, input().split())
        coins.append((p, n))

    for coin, cnt in coins:
        for money in range(T, 0, -1): # T원부터 1원까지 내려가며 진행 
            for i in range(1, cnt+1): # 현재 동전 coin의 개수만큼 for문 진행 
                if money - coin * i >= 0: # 0원 이상인 경우
                    dp[money] += dp[money - coin * i]

    print(dp[T])