백준-9084 동전문제 (파이썬)

문제

 

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

 

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

 

코드

import sys
n = int(sys.stdin.readline())

for _ in range(n):
    coinTotal = int(sys.stdin.readline())
    coinList = list(map(int, sys.stdin.readline().split()))
    totalMoney = int(sys.stdin.readline())
    dp = [0] * (totalMoney + 1)

    dp[0] = 1
    for coin in coinList:
        for i in range(1, totalMoney + 1):
            if i >= coin:
                dp[i] += dp[i - coin]
    print(dp[totalMoney])

시행착오 및 해결방안

동전의 갯수에 상관없이, 모든 경우의 수를 세어야하기 때문에 dp를 활용했다. dp의 크기는 경우의 수가 1원에 맞췄을 때 적어도 금액의 수를 넘을 수 없기 때문에 dp[금액]으로 설정한다. dp의 실행 과정을 이해할 때 모든 동전의 갯수를 2중 for문으로 돌릴때 1차원으로 이해하지 않고 2차원 table로 이해하면 쉽다.

예시) 금액 6원에 사용할 동전은 2원, 3원이라고 하자.

table
   0  1  2  3  4  5  6
2  1  0  1  0  1  0  1
3  1  0  1  1  0  1  2

 

이렇게 2차원 테이블로 표현할 수 있다. 2원, 3원 각각으로 만들 수 있는 0원은 0개 사용하면 되니 1로 설정한다. 그리고 3원 없이 2원으로만 우선 0~ 6원까지 2원만으로 만들 수 있는 갯수를 카운트한다.

   0  1  2  3  4  5  6
2  1  0  1  0  1  0  1

 

여기서 규칙은 dp[i]번째는 dp[i - 코인]의 합이다. 그전의 값을 더하면 계속 누적된 값을 구할 수 있다. 그 다음 3원의 값을 구해야하는데 0에서 시작이 아닌 2의 누적된 값을 활용해 더해간다. 따라서 6원이 2인 이유는 dp[6] = dp[6-3] => 1이기 때문에 1+1인 것이다.

   0  1  2  3  4  5  6
2  1  0  1  0  1  0  1
3  1  0  1  1  0  1  2