백준 문제풀이
2294번: 동전 2 / gold 5 / DP
RonLee
2023. 2. 27. 16:18
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주
www.acmicpc.net
'''
2294번: 동전 2 / gold 5 / DP
'''
INF = int(1e9)
n, k = map(int, input().split())
coin = []
for _ in range(n):
coin.append(int(input()))
dp = [INF for _ in range(k + 1)]
dp[0] = 0
for c in coin:
for i in range(1, k + 1):
if i - c >= 0:
dp[i] = min(dp[i], dp[i - c] + 1)
if dp[-1] == INF:
print(-1)
else:
print(dp[-1])
DP 알고리즘 사용
- 코인을 하나씩 꺼내고,
- DP 인덱스(동전 가치) 를 갱신하기