[백준/다이나믹 프로그래밍 2] - 동전

문제 링크

코드

# 동전을 최소로 사용해서 m원을 만드는게 아님
# m원을 만들 수 있는 가짓수를 구하는 것.
# dp[i] = i원을 만들 수 있는 가짓수
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(coin, m + 1):
            dp[i] += dp[i - coin]
            
    print(dp[m])

풀이

문제의 목표

• m원을 만들 수 있는 가짓수를 구하기

m원을 만드는데 필요한 동전의 가짓수의 최솟값이 아님에 유의하자.

현재 가지고 있는 동전들 중에서 하나를 선택하고, 선택한 동전의 가치에서 m원까지 만들어본다. 이를 모든 동전에 대해서 반복한다.

점화식은 아래와 같다.
dp[i] = i원을 만들 수 있는 가짓수

e.g. 5원 짜리 동전, m = 12

• dp[5] += dp[0] ➡️ 1
• dp[6] += dp[1] ➡️ 0
• dp[7] += dp[2] ➡️ 0
• ...
• dp[10] += dp[5] ➡️ 1 (= 5원 짜리 동전 2개를 사용한다.)
• ...

e.g. 7원 짜리 동전, m = 12

• dp[7] += dp[0] ➡️ 1
• dp[8] += dp[1] ➡️ 0
• dp[9] += dp[2] ➡️ 0
• dp[10] += dp[3] ➡️ 1 (= 5원 짜리 동전으로 만들 수 있는 경우의 수가 포함된다)
• dp[11] += dp[4] ➡️ 0
• dp[12] += dp[5] ➡️ 1 (= 5원 + 7원)