[이코테] 다이나믹 프로그래밍 - 효율적인 화폐 구성

4/4 Pr. 효율적인 화폐 구성

난이도 🌕🌕🌑 | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB

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

입력 조건

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

출력 조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.
• 불가능할 때는 -1을 출력한다.

입력 예시

2 15
2
3

3 4
3
5
7

출력 예시

5

-1

해설

그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다. 그러나 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결 불가능하고 DP를 이용해야 한다.

이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수를 $a_i$, 화폐의 단위를 k라고 했을 때,

$a_{i-k}$는 금액 (i - k)를 만들 수 있는 최소한의 화폐 개수를 의미한다.

• $a_{i-k}$를 만드는 방법이 존재하는 경우, $a_i=min(a_i,a_{i-k}+1)$
• $a_{i-k}$를 만드는 방법이 존재하지 않는 경우, $a_i=10,001$

이 점화식을 모든 화폐 단위에 대하여 차례때로 적용하면 된다. 실제로 문제를 풀기 위해서는 가장 먼저 K의 크기만큼 리스트를 할당한다. 이후에 각 인덱스를 ‘금액’으로 고려하여 메모이제이션을 진행한다. 예를 들어 N = 3, K = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 생각해보자.

• steps

  Step 0

  초기화 : 각 인덱스에 해당하는 값으로 10,001을 설정한다. 10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다. M의 최대 크기가 10,000이므로 불가능한 수로 10,001이라는 값을 설정했으며 이보다 더 큰 수여도 상관없다. 또한 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로 0을 설정한다. 따라서 초기 리스트의 값은 다음과 같다.

  

  Step 1

  화폐 단위 : 2, 3, 5 가장 먼저 첫 번째 화폐 단위인 2부터 확인한다. 앞서 언급한 점화식에 따라 다음과 같이 리스트가 갱신된다. 예를 들어 인덱스 2의 경우 1이라는 값을 가지는데, 이는 2원짜리 화폐 하나를 이용하여 2원을 만들 수 있다는 의미이다. 다시 말해 $a_2=a_0+1$이다. 인덱스 4의 경우 2라는 값을 가지는데, 이는 2원짜리 화폐를 2개 이용하여 (2 + 2) = 4원을 만들 수 있다는 의미이다. 다시 말해 $a_4=a_2+1$이다. 몇 인덱스의 경우 10,001의 값을 그대로 가지는데, 이는 2원짜리 화폐를 가지고 구성할 수 없는 금액이기 때문이다. 예를 들어 인덱스 3의 경우 인덱스 1의 값이 10,001이므로 마찬가지로 10,001의 값을 가진다.

  

  Step 2

  화폐 단위 : 2, 3, 5 이어서 화폐 단위 3을 확인한다. 앞서 언급한 점화식에 따라서 값을 도출하면 다음과 같이 리스트가 갱신된다. 예를 들어 $a_5=a_2+1$로 2라는 값을 가진다. 이것은 2원짜리 화폐 1개, 3원짜리 1개로 (2 + 3) = 5원을 만들 수 있다는 의미가 된다.

  

  Step 3

  화폐 단위 : 2, 3, 5 이어서 화폐 단위 5를 확인한다. 앞서 언급한 점화식에 따라서 값을 도출하면 다음과 같이 리스트가 갱신된다. 예를 들어 $a_7=a_2+1$로 2라는 값을 가진다. 이는 2원짜리 화폐 1개, 5원짜리 화폐 1개로 (2 + 5) = 7원을 만들 수 있다는 의미가 된다. 원래 이전 단계에서 $a_7$의 값은 3이었는데, 이는 (2 + 2 + 3) = 7원으로 3개의 화폐를 사용했을 때를 나타낸 것이다. 다만, 현재 단계에서 (2 + 5) = 7원을 만들면 화폐를 2개를 사용해도 되므로, 더 작은 값으로 갱신된다.

  

결과적으로 7원을 만들기 위한 최소의 화폐 개수는 2개이다. 앞서 언급한 점화식을 그대로 소스코드로 옮기면 다음과 같다. 또한 아래 코드에서 d[j - array[i]]가 10001인지 검사하는 부분은 사실 없어도 되는 코드인데, d[j - array[i]]가 10001의 값을 가지더라도 min(d[j], d[j - array[i]] + 1)은 항상 d[j]의 값을 반환하기 때문이다. 다만, 이해를 돕기 위해 코드에는 그대로 넣어주었다.

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])