[백준/파이썬] #2294

오늘도 30분 안에 풀었다! 

 

동전으로 금액 만들기는 DP 단골 유형이라 대강의 풀이 방법이 생각난 덕이 컸다. 

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coin = int(input())
    if coin not in coins:
        coins.append(coin)

coins.sort()
DP = [1e9] * (k+1)
smallest_coin = min(coins)
largest_coin = max(coins)

for i in range(smallest_coin, k+1):
    if i <= largest_coin:
        if i in coins:
            DP[i] = 1
            continue
    for coin in coins:
        if coin > i:
            break
        DP[i] = min(DP[i], DP[i-coin] + 1)


DP[k] = -1 if DP[k] == 1e9 else DP[k]
print(DP[k])