[백준] 9084 동전 (파이썬)

 

9084번: 동전

문제

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

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

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

3
2
1 2
1000
3
1 5 10
100
2
5 7
22

예제 출력 1 복사

501
121
1

 

---

DP 알고리즘 문제

 

첫 번째 입력을 보자면 1원 2원을 가지고 1000원을 만들건데, 이 금액을 만드는 모든 방법(가지수)의 개수를 물어보는거다

도저히 못 풀겠어서 풀이를 찾아보다 이 분의 해설을 보고 이해하였다.

출처는 마지막에 남길테니 참고하셔서 보길 바란다.

 

---

 

 

예를 들어 2원과 4원으로 8원을 만드는데 필요한 모든 방법을 구해보자.

우선 dp table을 만들고 행에는 우리가 가지고 있는 동전 (2원 4원), 열은 우리가 만들어야 하는 금액을 의미한다.

어떤 동전이든 0원을 만들 수 있는 가지수는 무조건 1가지가 존재하기 때문에 첫 번째 열은 1로 초기화한다.

 

 

4원을 생각하지 말고 우선 2원부터 생각해서 채워보자

2원으로 2원을 만들려고 할 때, 2원에서 내가 가진 동전(2원)을 빼버린다. 그 후에 2원을 뺀 나머지 금액으로 만들 수 있는 가지수를 살펴본다.

 

현재 나머지 금액은 0원이다. 즉 살펴보아야 할 dp칸은 dp[0]이다. ( dp[2-2] = dp[0])

2원으로 0원을 만들 수 있는 가지수는 무조건 1가지가 존재하기 때문에 2를 만들 수 있는 가지수는 dp[0]의 값인 1이 된다.

(dp[2] = dp[0] = 1)

 

 

2원으로 3원을 만들 수 있는 가지수는 3원 - 2원 = 1원, 2원으로 1원을 만들 수 있는 가지수는 0이기 때문에 dp[3]의 가지수는 0이 된다. dp[3-2] = dp[1] = 0

 

 

2원으로 4원을 만들 수 있는 가지수는 4원-2원 = 2원, 2원으로 2원을 만들 수 있는 가지수는 1이기 때문에 dp[4]의 가지수는 1이 된다. dp[4-2] = dp[2] = 1 

 

 

2원의 가지수는 이렇게 채울 수 있다.

 

4원으로 만들 수 있는 가지수도 살펴보장

4원 칸에서는 2원으로만 만들 수 있는 가지수를 4원 칸에 가지고 온 다음에 시작해야 한다

이렇게 해주면, 지금은 2원과 4원 둘 다 사용하는 셈이 된다.

 

 

4원으로 4원을 만들 수 있는 가지수는 dp[4-4] = dp[0] = 1의 값을 가져온다. 

근데 이미 2로 만들 수 있는 4의 가지수를 업데이트 했으므로 1+1= 2의 가지수를 가지게 된다.

 

 

4원으로 8원을 만들 수 있는 가지수는 dp[8-4] = dp[4] = 2의 값을 가져온다.

근데 이미 2로 만들 수 있는 8의 가지수를 업데이트 했으므로 2+1 = 3의 가지수를 가지게 된다.

 

2차원 dp table

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    coins = list(map(int,input().split()))
    coins.insert(0,0)
    amount = int(input())
    
    dp = [[0] *(amount+1) for i in range(n+1)]
    
    for i in range(n+1):
        #0원으로 만들 수 있는 가지 수는 1로 초기화
        dp[i][0] = 1
            
    for j in range(1,n+1):
        for i in range(1,amount+1):
            #처음에 만들었던 다른 coin의 가지수를 다음 coins 칸에 가지고 온다
            dp[j][i] = dp[j-1][i]
            #만들고 싶은 값에서 내가 지금 가진 동전을 뺀다.
            if i-coins[j] >= 0:
                dp[j][i] += dp[j][i-coins[j]]
    print(dp[n][amount])

 

1차원 dp table

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())
    coins = list(map(int, input().split()))
    m = int(input())
    
    dp=[0] * (m+1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(1, m+1):
            if i >= coin:
                dp[i] += dp[i-coin]

    print(dp[m])

 

 

참고(출처) 

[week04] 백준 9084번 python DP 천천히 이해해보기