백준 2294: 동전2 (Python)

접근

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

2294번: 동전 2

전형적인 DP 문제여서 점화식을 파악하는 과정이 중요했다. 이전 단계인 2293번 '동전 1' 문제를 풀고오면 조금 수월하게 접근할 수 있는것 같다.

합이 K 일 때, 사용한 동전의 최소 개수를 구하기 위하여, 합이 i 일 때 사용한 최소 동전의 개수를 구하는 작은 문제로 쪼개었다.

1. DP 배열을 K + 1 의 길이로 생성하고, DP[i]의 의미를 합이 i 일 때 사용한 최소 동전의 개수를 계산하여 갱신한다.
2. 갱신이 완료된 후, DP[K]의 값을 표시하고, 합을 K로 만들 수 없다면 -1을 출력한다.

가치가 i 인 동전을 사용할 때, 가치의 합이 j 인 칸을 갱신하기 위해서는 j - i 칸에 해당하는 동전의 갯수에 1을 더하거나(i 동전이 한개 더 사용되므로), 혹은 기존에 j 칸에 있던 값 중 작은 값으로 갱신하면 된다.

갱신할 때 작은 값이 사용되기 때문에 초기 값을 INF 로 두고, 갱신을 마친 후 DP[K] 값이 INF 라면 -1을 출력하면 된다.

코드

import sys

input = sys.stdin.readline
INF = float("inf")

N, K = map(int, input().split())
coinValue = [int(input()) for _ in range(N)]
dp = [INF] * (K + 1)
dp[0] = 0
for i in coinValue:
    for j in range(i, K + 1):
        if j - i >= 0:
            dp[j] = min(dp[j - i] + 1, dp[j])
print(dp[K] if dp[K] != INF else -1)

더 생각해 볼 것?

가치가 같은 동전이 여러번 주어질 수 있지만, 각각의 동전은 몇개라도 사용될 수 있기 때문에, 여러번 주어지는 것을 모두 입력하여 배열에 넣을 필요는 없다. 중복되는 코인을 삭제하면 순회가 줄어들기 때문에 시간을 줄일 수 있을 것이다. 백준에는 해당 과정을 추가하여 시간을 절약했지만, 간단한 과정이기 때문에 본문에는 추가하지 않았다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!