백준 2294 동전 2

문제 바로가기
골드 V (22.10.17 기준)

✏ 생각하기

문제에서 구하는 것은 n가지 종류의 동전이 주어졌을 때, 합이 k원이 되게하는 동전의 최소 개수이다. 동전은 종류별로 무한개로 주어져있다.
처음에는 단순히 동전 중 k원보다 작으면서 가장 큰 가치부터 사용할 수 있는 만큼 사용하는 단계를 반복하는 그리디로 풀면 되지 않을까 생각했다. 하지만 문제에서 주어진 예제 입력과 같이 예외가 발생한다.

예제 입력
3 15
1
5
12

출력
3

그리디로 생각하면 12원짜리 1개, 1원짜리 3개로 총 4개가 답이 되지만, 5원짜리 3개만으로 k(=15)를 만들어낼 수 있다. 따라서 좀 더 다양한 경우를 살펴봐야 한다는 것을 알 수 있다. 그렇다면 DP로 풀 수 있을지 생각해보자.
목표로 하는 값 k을 주어진 동전들로 만들 수 있다고 생각할 때, 다음과 같은 관계식을 생각할 수 있다.

현재 위 식에선 $coin$의 값이 하나로 안 정해지지 않는다. (예제 입력에서 보면, $15=12+(1+1+1)=5+(5+5)=\cdots$) 여기에 사용되는 동전이 최수개수라는 추가 조건을 고려해야 한다.
위 식으로부터 k'가 최소 개수의 동전으로 이루어져있다면 k도 최소 개수의 동전으로 이루어져 있다는 것을 알 수 있다. 따라서 작은 사건을 총합이 i(<=k)가 되는 최소 동전 개수로 설정하면 풀 수 있을 것이다.

📒 알고리즘

다음과 같은 DP 식을 세울 수 있다.

dp[i] = 총합이 i가 되는 최소 동전 개수
dp[0] = 0
dp[i] = min(dp[i-coin] for coin in coins)

⚠ 총합이 i가 되는 것이 불가능한 경우도 생각해야 한다.

💻 코드

import sys

n, k = map(int, sys.stdin.readline().split())
coins = []
min_coin = 100000
for i in range(n):
    coins.append(int(sys.stdin.readline()))
    min_coin = min(min_coin, coins[i])
    # 주어진 동전 중 가장 싼 것을 시작점으로 하기 위해 값 저장
    # 더 싼 값은 어차피 만들 수 없으므로 
if min_coin > k: 
    print(-1)
else: 
    dp = [-1] * (k+1)
    dp[0], dp[min_coin] = 0, 1
    for i in range(min_coin+1, k+1): 
        for j in range(len(coins)): 
            coin = coins[j]
            if i - coin >= 0 and dp[i-coin] != -1:  # 불가능한 경우 배제
                if dp[i] == -1:
                    dp[i] = dp[i-coin] + 1
                else: 
                    dp[i] = min(dp[i], dp[i-coin] + 1)
    print(dp[k])

👀 다른 풀이

dp 배열의 초기값을 100001(>k의 최대값)으로 둬서 불가능한 경우 dp[i]에 처음 접근한 경우(위 코드에서 if dp[i] == -1)를 따로 생각하지 않고 dp를 수행할 수 있다.