[백준 2294] 동전2 (Python)

 

코드

n, k = map(int, input().split())

coin = []

for i in range(n):
    coin.append(int(input()))
sum = [10001 for i in range(k+1)]
sum[0] = 0

for i in coin:
    for j in range(i, k+1):
        sum[j] = min(sum[j], sum[j-i]+1)

if sum[k] == 10001:
    print(-1)
else:
    print(sum[k])

동전 1과 비슷한 문제이지만 차이점은 동전의 최소 갯수를 구하는 점과 불가능한 경우엔 -1을 출력하는 것이다.

 

1. 일단 sum 리스트를 초기값 10001로 초기화 해준다.
2. i==j일 경우에는 동전을 1개만 뽑아도 되므로 sum[0]에 0을 넣어 sum[i-j]+1을 sum[j]에 넣을 수 있도록 한다.
3. 동전의 최소 갯수를 구하는 것이기 때문에 j값을 위한 동전의 갯수는 min(sum[j], sum[j-i] + 1)으로 하여 전의 동전의 갯수와 i값의 동전이 있는 경우의 동전의 갯수중 더 작은 갯수를 넣는다.

 

이것도 어려웠다... 동전1과 유사한 문제임에도 로직을 생각해내는게 왜이렇게 어려운지..!

 

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

2294번: 동전 2