[Python] 백준 2294번 : 동전 2

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

2294번: 동전 2

---

💡 문제 풀이

DP 문제이다! DP 문제는 항상 3가지를 고려해준다.

1. 어떤 값을 memoization 할지

2. 어떻게 점화식을 세울지

3. 초기값을 어떤 값으로 둘지

 

이번 DP 배열에는 n을 만드는데 최소 동전 개수를 넣어주었다.

동전의 가치가 i 보다 크면 DP[i]와 DP[i-c] + 1을 비교해서 더 작은 값으로 최신화를 한다.

더 작은 값으로 최신화하기 때문에 DP 배열을 최댓값보다 1 큰 값으로 초기화했다.

✔️ 느낀 점

역시 어떤 값을 넣을지만 잘 생각해도 반은 넘어가는 것 같다.

동전 1 문제를 풀어서 이번 건 조금 쉽게 풀었다.

💻 코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
DP = [100001 for _ in range(k+1)]
DP[0] = 0

for c in coins:
    for i in range(1, k+1):
        if i-c>=0:
            DP[i] = min(DP[i], DP[i-c] + 1)

print(-1) if DP[k] == 100001 else print(DP[k])