[Python] 효율적인 화폐 구성

문제

• N가지 종류의 화폐가 있다.
• 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
• 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력

• 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
• 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력

• 첫째 줄에 경우의 수 X를 출력한다.
• 불가능할 때는 -1을 출력한다.

입력 예시

2 15
2
3

출력 예시

5

문제 풀이

• dp테이블의 i는 i값을 만드는 데  필요한 최소 동전의 개수이다.
  • dp[2] = 1인 경우, 2원을 만드는 데 필요한 최소 동선의 개수는 1개라는 뜻
• 따라서 화폐의 단위가  k일 때, [i - k)]값은 k로 만든 이전 값의 최소 동전 개수이다.
• 따라서 [i - k]값이 10001이 아니라면, [i]의 값을 [i - k] + 1로 갱신하면 된다.
• 점화식은 아래와 같다

dp[j] = min(dp[j], dp[j - array[i]] + 1)

코드

n, m = map(int,input().split())
array = []
for _ in range(n):
    array.append(int(input()))
dp = [10001] * (m + 1)

# 동전의 개수만큼 탐색
dp[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        # [j - array[i]] + 1로 갱신
        if dp[j - array[i]]!= 10001:
            dp[j] = min(dp[j], dp[j - array[i]] + 1)

if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])