[백준][Python][2294][DP] 동전 2

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

2294번: 동전 2

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

2293번: 동전 1

 

동전 1 문제와 다른 점은, 동전 1의 경우 모든 경우의 수를, 동전 2 의 경우에는 동전을 가장 적게 쓰는 경우의 수 를 구한다.

따라서 몇가지 달라지는 점이 있는데,

동전 1은 value[x] += value [x-c]로 모든 경우의 수를 더하는데,

동전 2는  value[x] = min(value [x], value [x-c]+1)로 최소 개수를 더한다.

 

DP 배열을 구하는 for문의 순서도 달라지는데,

동전 1은 동전 종류 -> 1-k 를 만드는 수 순서로,

동전 2는 1-k를 만드는 수 -> 동전 종류의 for 문을 돌게 된다.

 

점화식은 value[x] = min(value [x], value[x-c]+1) 인데, 이 점화식의 의미는 동전 c 를 쓰면 동전 사용 최솟값을 만들수 있을까? 이다.

Yes : value[x-c]+1  -> x 값에서 동전값 c를 뺀 것 + 동전 1개 추가

No: value[x] -> 존-버

 

주의할 점도 있다.

1. 동전 리스트를 가지고 목표값 k를 못만들면 -1 출력 -> 초기값이 안변하면 -1 출력
2. 동전 리스트에서 중복된 동전이 있을수 있다. -> set 으로 해결

import sys

n, k = [int(i) for i in sys.stdin.readline().split()]
coins = []
for _ in range(n):
    coins.append(int(sys.stdin.readline()))

coins = list(set(coins))
coins.sort()

value = [9912341234]*(k+1)
value[0] = 0

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


print(-1 if value[-1] == 9912341234 else value[-1])