백준 2294번 python 풀이 - 동전2

문제 링크

2294번

해결책

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

coins = []
for i in range(n):
    coin=int(sys.stdin.readline().rstrip())
    if coin not in coins and coin <= k:
        coins.append(coin)

coins.sort()

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


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

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

주석으로 달 설명

DP를 이용한 해결. 왜 그래프로 왔는지 정확히는 모르겠지만, 이거를 그래프로 해결한다면 DFS가 어울릴 것 같다.

해설 영상 해설 블로그 둘을 참고해도 좋다.