[백준] 2294번 동전 2 파이썬 정답 풀이

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

2294번: 동전 2

---

1. 접근 방식

• 작은 문제들을 모아 큰 문제를 해결하는 다이나믹 프로그래밍 기법이다

k원을 구성하는 최소 동전들의 개수는 (k - coin)원을 구성하는 최소 동전 + 1이다. 따라서 1원부터 k원까지 점진적으로 각 금액을 구성하는 최소 동전 개수를 구하면 문제를 해결할 수 있다.

 

 

• 인덱스 i원을 만드는 최소 동전 개수를 담은 1차원 dp 배열을 선언하자

최소 동전 개수를 구하는 것이므로, 초기값은 임의의 큰 수 99999로 설정한다.

여러 가지 동전들을 조합하여 i원을 만들면, 그때 사용한 동전 개수, 즉 dp[i]는 무조건 99999보단 작다.

만약 동전을 어떻게 조합해도 i원을 만들지 못한다면 dp[i] 값은 여전히 99999일 테고, 결국 동전들로 i원을 만들 수 없다는 의미이므로 dp[i]에 -1을 할당한다.

 

 

 

2. 정답 코드

import sys

input = sys.stdin.readline
INITIAL = 99999

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

dp = [INITIAL] * (k + 1)
dp[0] = 0

for i in range(1, k + 1):
    for coin in coins:
        if coin > i:
            break

        if dp[i - coin] > -1:
            dp[i] = min(dp[i], dp[i - coin] + 1)

    if dp[i] == INITIAL:
        dp[i] = -1

print(dp[k])