[백준] 2293 - 동전 1

문제 설명

문제 링크

n개의 동전 종류가 주어지며, 이를 사용하여 특정 수 k를 만드는 조합의 개수를 구하는 문제이다.

문제 풀이

전에 했던 동적계획법 문제와 어느 정도 유사성을 띄는 문제다.

1, 2, 3 더하기 4

다만, 위의 문제에서는 1, 2, 3으로 사용할 수 있는 숫자가 고정되어 있었던 반면 이번 문제에서는 주어지는 동전의 액면가가 랜덤이라는 것이다. 여기에 더해, 주어지는 동전 종류도 개수가 정해져있지 않기 때문에 2차원 배열로는 시도조차 못할 것 같아서 자연스레 1차원 배열로 만들 생각을 했다.

동적 계획법 문제는 우선 상수로 무언가가 주어져야 이를 기반으로 점화식을 세우는데, 이 부분이 생각보다 오래 걸렸다. 주어진 조건이 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000 여서 더욱 헷갈렸던 것 같다. 0을 만드는 데 사용되는 동전 조합의 개수는 아무 동전도 사용하지 않는 한 가지 방법, 즉 1이라는 것을 생각하여 cache[0] = 1로 설정하여 진행했다.

문제에서 주어진 1, 2, 5는 뭔가 너무 간단하여 나조차도 설득이 안될 것 같아 2, 5, 7로 진행했다.

특정 수 k에서 동전의 액면가를 뺀 k-coin값이 있을 것이다. coin = 2일 때 dp 테이블은 [1,0,1,0,1,0,1,0]이다.

dp[2] += dp[2-2] : dp[2] = 1
dp[4] += dp[4-2] : dp[4] = 1
dp[6] += dp[6-2] : dp[6] = 1
dp[7] += dp[7-2] : dp[7] = 0

coin = 5일 때는 기존의 2로 했을 때의 값들에 더해 [1,0,1,0,1,1,1,1]이 된다.

dp[5] += dp[5-5] : dp[5] = 1
dp[6] += dp[6-5] : dp[6] = 1
dp[7] += dp[7-5] : dp[7] = 1 (7-5 = 2, dp[2] = 1)

마지막으로 coin = 7일 때는 다음 하나의 경우의 수만 추가된다:

dp[7] += dp[7-7] : dp[7] = 2

코드

import sys
input = sys.stdin.readline

def dp(k, coins):
    cache = [0] * (k+1)
    cache[0] = 1

    for coin in coins:
        for i in range(coin, k+1):
            cache[i] += cache[i-coin]
    
    return cache[k]

n, k = map(int, input().split())
coins = []

for _ in range(n):
    coins.append(int(input()))

coins.sort()

print(dp(k, coins))