[BOJ][python] 2294. 동전 2

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

2294번: 동전 2

---

💡IDEA

동적 계획법을 사용하는 문제이다.

2022.07.21 - [Algorithm/BOJ] - [BOJ][python] 2293. 동전 1 문제를 풀었던 것이 도움이 되었다.

가치의 합이 최대 10000이므로 10001 길이의 dp 배열을 사용해야 한다. 가치의 합이 0인 경우는 없으므로 0으로 초기화하고, k번째까지 dp를 구한다.

현재 동전을 포함하는 경우와 포함하지 않는 경우를 생각해야 한다. 현재 동전을 포함하는 경우는 i번째 전의 값에 현재 동전을 포함해서 +1 한 값, 현재 동전을 포함하지 않는 경우는 이전까지 사용한 동전만 센 값이다.

dp를 모두 갱신했음에도 마지막 값이 10001이라면 실패한 것이므로 -1을 출력하고, 그보다 작으면 dp의 마지막 값을 출력한다.

 

📌CODE

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = sorted([int(input()) for _ in range(n)])

dp = [10001]*(k+1)
dp[0] = 0
for i in coins:
    for j in range(i, k+1):
        dp[j] = min(dp[j], dp[j-i]+1)

if dp[-1]>10000:
    print(-1)
else:
    print(dp[-1])