백준, 동전 2, 22964, 파이썬

[유형]

DP

 

[문제링크]

https://www.acmicpc.net/problem/2294

 

[요약]

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

 

[문제풀이]

동전의 구성이 1,5,10일때 가치의 합이 15가 되는 동전 최소 개수

동전 1을 통해 1~15원까지 만들 수 있는 동전의 최소 개수는 각각 1,2,3,...,10이다. 따라서, dp[i]=i로 갱신된다.

동전 5가 추가되었을 때, dp[4]까지의 값은 더 이상 갱신되지 않는다.

dp[5]는 min(dp[5],dp[5-5]+1)이라고 할 수 있다. 5 1개만으로 5원을 만들 수 있다.

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()

N, M = map(int, input().split())
coins = []
for _ in range(N):
    coins.append(int(input()))

coins.sort()

dp = [10001]*(M+1)
dp[0] = 0

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

if dp[-1] == 10001:
    print(-1)
else:
    print(dp[-1])