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