[백준] 2294 동전2 파이썬

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

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

2294번: 동전 2

 

---

풀이

이전에 한 번 못 풀어서 다른 사람 코드를 봤던 문제였다.

이번엔 안 보고 풀어봤다.

 

1. dp 배열을 0으로 초기화한다.

2. k+1까지 순회하며 i원의 최소 동전 개수를 저장한다.

    2-1 dp[ i - 동전가치 ] 중 가장 작은 값에 1을 더한 값이 dp[i]의 최소값이다.

         ex) 동전 종류 = [1, 3] 일 때 dp[5] = min(dp[4], dp[2]) + 1

3. k+1번째까지 순회를 마치면 출력한다.

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = []
for i in range(n):
    a = int(input())
    if a <= k:
        coins.append(a)

dp = [0] * (k+1)

for i in range(1, k+1):
    if i in coins:
        dp[i] = 1
        continue
    minCoin = []
    for j in coins:
        if i > j and dp[i-j] != 0:
            minCoin.append(dp[i-j])
    if minCoin:
        dp[i] = min(minCoin) + 1

if dp[k]:
    print(dp[k])
else:
    print(-1)

처음엔 탑 다운으로 설계해봤다가, 바텀 업 방식이 더 효율적일 것 같아 그렇게 바꿨다.

자꾸 92퍼에서 틀리길래 반례 다 뒤져보면서 삽질했는데

알고보니 불가능할 경우 -1을 출력하라는 문구를 못 본 것 때문이었다 ..