[Python] 백준/BOJ 9084번: 동전 (Gold 5)

💻 Problem

문제 보러 가기

 

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

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

 

💡 Approach

dp 배열에서 index는 현재 금액이고 value는 N가지 동전으로 현재 금액을 만들 수 있는 방법의 수이다.

 

예를 들어, 2원과 4원으로 8원을 만든다고 하겠다.

• N=2, coins=[2, 4], M=8

우리가 간단히 생각해 본다면 2+2+2+2, 2+2+4, 4+4 세 가지 방법이 가능할 것이다.

 

이걸 dp로 확인해보자.

일단 dp[0]을 1로 초기화한다.

 

2원으로 만들 수 있는 금액들을 표시한다.

1원부터 8원까지 탐색하면서 현재 index에서 동전 금액만큼 뺀 index의 value을 더한다. (방법을 추가한다)

dp[2], dp[4], dp[6], dp[8]이 1이 될 것이다.

 

그다음, 4원으로 만들 수 있는 금액들을 표시한다.

마찬가지로 1원부터 8원까지 탐색한다. (방법을 추가한다)

이전에 2원으로 만들 수 있는 금액들을 표시했으므로 2원과 4원으로 같이 만들 수 있는 금액도 표시된다.

dp[4], dp[6]이 2가 되고, dp[8]이 3이 된다.

• dp[4]의 경우, 원래 2로 만들 수 있는 방법 한 가지(2+2)로 기록되어 있었는데 4원을 탐색하면서 4로 만들 수 있는 방법 한 가지(4)를 추가한다.
• dp[6]의 경우, 원래 2로 만들 수 있는 방법 한 가지(2+2+2)로 기록되어 있었는데 4원을 탐색하면서 4로 만들 수 있는 방법 한 가지(2+4)를 추가한다.
  • dp[2]가 1로 기록되어 있으므로 4원을 추가하여 dp[6]을 기록할 수 있다.
• dp[8]의 경우, 원래 2로 만들 수 있는 방법 한 가지(2+2+2+2)로 기록되어 있었는데 4원을 탐색하면서 4로 만들 수 있는 방법 두 가지(2+2+4, 4+4)를 추가한다.
  • dp[4]에 2+2, 4 두 가지 방법이 기록되어 있었으므로 이에 4를 더하여 8에 추가적으로 기록한다.

 

✏️ Solution

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])

• 시간복잡도: O(N * M) = O(20 * 10^4) = O(2 * 10^5)