[백준2294번] 동전 2 / Python3

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3 15
1
5
12

예제 출력 1 복사

3

나의 풀이

전형적인 냅색 알고리즘 문제이다. k+1 크기의 동전의 최소 개수를 담을 dp배열을 모든 값이 sys.maxsize 의 값으로 선언하고 0번 인덱스의 요소만 0으로 초기화를 해준다. 이후 동전의 가치를 정렬하여 작은 수부터 차례로 dp를 채워나간다. dp를 채울때의 점화식은 dp[j] = min(dp[j], dp[j - 동전의 가치] + 1이다. 즉, 이전 동전의 가치로 만들 수 있는 개수와 현재 동전 하나와 현재 동전의 가치를 뺀 상태에서의 최소 개수를 더한 것중 작은 것으로 최신화를 시켜주는 것이다. 이렇게 모든 동전의 가치를 반복하고 dp배열의 마지막 원소가 동전의 최소 개수가 된다. 만약, 마지막 원소가 sys.maxsize라면 주어진 동전의 가치들로는 해당 합을 만들 수 없다는 의미이므로 -1을 출력한다.

단, 여기서 주의할 점은 문제에서 가치가 같은 동전이 여러 번 주어질 수도 있다라고 언급하였다. 따라서 coin을 입력받을 때 중복을 제외해주어야한다.

코드

# 2294번 동전 2
import sys

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

coins = []
for _ in range(n):
    tmp = int(input())
    if not tmp in coins:
        coins.append(tmp)
coins.sort()

dp = [sys.maxsize] * (k+1)
dp[0] = 0
for i in range(len(coins)):
    for j in range(coins[i], k+1):
        dp[j] = min(dp[j], dp[j-coins[i]]+1)

if dp[-1] == sys.maxsize:
    print(-1)
else:
    print(dp[-1])