백준: 2294 동전 2

문제

2294번: 동전 2

 

문제 풀이

 앞서 다룬 동전 1은 동전을 합하여 K가 되는 경우의 수를 찾는 문제였지만, 이 문제는 동전을 합하여 K가 될 때, 최소의 동전을 사용하여 K가 되는 경우를 반환하는 문제이다.

 

 

위와 같이 동전의 가치에 따라, 사용하여야 되는 동전의 개수를 구할 수 있다. 앞서 다룬 동전 1은 동전의 합이 K가 되는 경우의 수를 찾기 위해 경우의 수들을 누적하였다. 이와 달리 이 문제에서는 최초에 가장 작은 가치의 동전으로 금액을 나타낼 수 있는 동전의 수를 구하고, 다음의 가치에 대해서는, 현재 메모이제이션 된 값과 해당 동전으로 나타낼 수 있는 경우를 비교하여 최소 값을 기록해두는 방식을 사용한다.

 

 예를 들어, 2를 2인 동전으로는 1개, 1인 동전으로는 2개를 사용하여야 한다. 따라서 작은 값인 1을 2를 나타낼 수 있는 최소 동전수로 기록한다. 또한 나머지 금액들은 (10 - 2), (8 - 2), (6 - 2), (4 - 2)와 같이 이전에 메모이제이션 된 값을 활용하여 구할 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n, k = map(int, stdin.readline().split())
    coins = [int(stdin.readline()) for _ in range(n)]
    dp = [0] + [k + 1] * k

    for coin in coins:
        for price in range(coin, k + 1):
            dp[price] = min(dp[price], dp[price - coin] + 1)

    print(dp[k] if dp[k] != k + 1 else -1)