백준 9084: 동전 (Python)

문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

해설

DP를 활용해 푸는 냅색 유형의 문제다.

우선, 우리는 이게 왜 DP 문제인지 생각해보아야 한다.

 

 

예를 들어, 1원짜리 동전과 2원짜리 동전이 있다.

이 동전으로 각각 1원, 2원, 3원을 만드는 상황을 생각해보자. 그러면 다음과 같을 것이다.

 

(1원) 동전을 사용하는 경우, (1원/2원) 동전을 사용하는 경우로 나누어 두 줄로 나타내보았다.

(1원/2원) 동전을 사용해 3원을 만드는 경우를 들여다보자.

• 1원을 만드는 방법: 1원짜리 동전 1개
• 2원을 만드는 방법: 1원짜리 2개, 2원짜리 1개
• 3원을 만드는 방법: 1원짜리 3개, 1원짜리 1개 + 2원짜리 1개

여기서 주목할 점은, 3원을 만드는 경우에 기존의 1원과 2원으로 만들 수 있는 조합을 활용한다는 것이다.

 

즉, 큰 문제(3원 만들기)를 작은 문제(1원 만들기)로 쪼개어 해결하는 구조이므로 DP 문제라고 볼 수 있다.  

 

알고리즘 설계

이 문제의 해결을 위한 DP 배열을 DP[i][j]라고 정의해보자. 여기서 i는 사용하는 동전의 종류, j는 만들어야 하는 금액이다.

DP[i][j]는 i 종류의 동전을 사용해서 j원을 만드는 방법의 수를 의미한다.

DP 배열을 채우는 공식은 다음과 같다.

• 만약 j가 현재 동전의 가치보다 작다면, DP[i][j] = DP[i-1][j]
• 그렇지 않다면, DP[i][j] = DP[i-1][j] + DP[i][j-현재 동전의 가치]

그러면, (1원/2원/5원) 동전을 가지고 10원을 만드는 방법의 수를 구한다고 했을때 DP 테이블은 다음과 같이 나타날 것이다.

코드

T = int(input())

for i in range(T):
    N = int(input()) # 동전의 종류 개수
    coins = list(map(int, input().split()))
    M = int(input()) # 만들어야 할 금액
    DP = [[0] * (M+1) for _ in range(N+1)]
    DP[0][0] = 1 # 0원짜리로 0원을 만드는 경우의 수 1 추가

    coins = [0] + coins # padding, 0원 짜리 동전이 있다고 생각하기
    for i in range(1, N+1): # 동전 종류
        for j in range(M+1): # 가치 1~M
            coin = coins[i]
            if j < coin:
                DP[i][j] = DP[i-1][j]
            else:
                DP[i][j] = DP[i-1][j] + DP[i][j-coin]

    print(DP[N][M])