728x90
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주
www.acmicpc.net
동전1 문제 풀면 동전2는 금방 풀 수 있다.
역시
재밌다.
INF = 987654321
n,k = map(int,input().split())
coins = []
for _ in range(n):
coins.append(int(input()))
dp = [INF]* (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] == INF:
print(-1)
else:
print(dp[k])728x90
'알고리즘 > DP' 카테고리의 다른 글
| [Python] 백준 1520 - 내리막 길 (0) | 2023.01.30 |
|---|---|
| [Python] 백준 9456 - 스티커 (0) | 2023.01.29 |
| [Python] 백준 1890 - 점프 (0) | 2023.01.28 |
| [Python] 백준 12852 - 1로 만들기 2 (0) | 2023.01.21 |
| [Python] 백준 2293 - 동전 1 (0) | 2023.01.18 |