Algorithm/DP

[백준] 2294번 : 동전 2 (파이썬)

_은선_ 2024. 2. 18. 01:52
728x90
SMALL

DP 문제

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

 

2294번: 동전 2

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어

www.acmicpc.net

 

💡 풀이 코드

import sys

n, k = map(int, sys.stdin.readline().split())
coin = []
for _ in range(n):
    value = int(sys.stdin.readline())
    coin.append(value)

dp = [10001] * (k + 1)
dp[0] = 0
def coin2(n, coin, k):
    for i in range(1, k + 1):
        for j in range(n):
            if i < coin[j] : continue
            dp[i] = min(dp[i], dp[i - coin[j]] + 1)
coin2(n, coin, k)

print(dp[k] if dp[k] != 10001 else -1)
728x90
LIST
저작자표시