[이코테] 효율적인 화폐 구성 - 구체적 풀이

문제

• 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

3 4
3
5
7

출력 예시

5

-1

 

 

---

풀이과정

import sys

# 정수 N, M을 입력 받기
n, m = map(int, sys.stdin.readline().rstrip().split())

# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

# 한 번 계산된 결과를 저장하기 위한 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])

 

이 코드는 다이나믹 프로그래밍(DP)을 사용하여 주어진 화폐 단위로 금액 `m`을 만들 때 필요한 최소 동전 개수를 계산하는 문제를 해결하는 코드입니다.

다이나믹 프로그래밍

이제 각각의 화폐 단위를 하나씩 선택하여 `d` 배열을 업데이트합니다.

중첩된 반복문을 사용하여 모든 화폐 단위와 금액을 고려합니다.

   - 바깥쪽 반복문(`for i in range(n):`)은 화폐 단위를 선택하는 역할을 합니다.
   - 안쪽 반복문(`for j in range(array[i], m + 1):`)은 현재 화폐 단위를 사용하여 가능한 모든 금액을 순회합니다.

if d[j - array[i]] != 10001

 

조건을 확인하여, 현재 금액 j 원을 만들기 위해 현재 화폐 단위 array[ i ]를 사용할 수 있는 경우에만 아래의 동작을 수행합니다.

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

 

현재 금액 j 원을 만드는데 필요한 최소 동전 개수를 업데이트합니다.

 

여기서 j 는 현재 금액을 나타내고, array[ i ]는 현재 선택한 화폐 단위를 나타냅니다. 위 코드는 현재 금액 j 를 만들기 위해 최소 동전 개수를 구하는데, 이전에 계산된 동전 개수 d [ j - array[ i ] ]에 1을 더한 것입니다.
 

j - array[ i ] 이렇게 빼는 이유는 다이나믹 프로그래밍을 사용하여 동전을 조합하여 금액을 만들 때,

현재 화폐 단위를 사용하고 남은 금액을 만들 때 필요한 동전 개수를 계산하기 위함입니다.

 

남은 금액을 만드는 이유는 이미 계산된 부분 문제의 결과를 활용하여 새로운 부분 문제를 효율적으로 해결하기 위함입니다.

예를 들어

• 현재 화폐 단위가 5원이고, 금액이 11원(d [11])이라고 가정해봅시다. 
• 이때 남은 금액은 11 - 5 = 6원입니다. 
• 따라서 현재 화폐 단위 5원을 사용하려면, 남은 6원은 몇개의 최소 동전 개수였는지 저장된 기록을 가져옵니다.
• 남은 6원을 만드는 최소 동전 개수는 d[6] 에 저장되어 있으며, 이 값에 현재 화폐 단위를 사용한 횟수인 1을 더하여 현재 금액 11원을 만들 때 필요한 최소 동전 개수를 계산할 수 있습니다.

 

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

우리가 화폐 단위로 1원, 3원, 4원 세 가지 동전만 가지고 있다고 가정하고, 금액 6원을 만들어야 한다고 합시다.

1. 1원 동전을 사용하면 6원을 만들기 위해 1원 동전 6개를 사용할 수 있습니다. 따라서 d[6] = 6이 됩니다.
2. 3원 동전을 사용하면 6원을 만들기 위해 3원 동전 2개를 사용할 수 있습니다. 따라서 d[6] = 2가 됩니다.

이제 d[6]을 비교해봅시다. 우리는 최소한의 동전 개수로 금액 6원을 만들고 싶습니다. 그러므로 최소값을 선택해야 합니다.

 

d[6] = 6 : 1원 동전 6개 사용.
d[6] = 2 : 3원 동전 2개 사용.

 

따라서 min 함수를 사용하여 최소값을 선택하면 d[6] = 2가 됩니다. 이것은 3원 동전 2개를 사용하여 6원을 만드는 것이 더 적은 동전 개수로 가능하다는 것을 나타냅니다.
이렇게 각 상태마다 최소값을 선택하여 DP 테이블을 업데이트하면, 최적해를 구할 수 있습니다.

 

구체적으로 과정을 보고싶으면 더보기를 클릭하시면 됩니다.

1. 초기값 설정:
   - d[0] = 0 (0원을 만드는데 필요한 동전 개수는 0개로 초기화)

2. 첫 번째 화폐 단위 1원을 고려합니다:
   -  i = 1일 때, array[1] = 1
   - 이제 금액 1원부터 6원까지 각각을 만들어 보면서 d 배열을 업데이트합니다.

   - 금액 1원을 만드는 경우: d[1] = min(d[1], d[0] + 1) (1원 동전 1개 사용)
   - 금액 2원을 만드는 경우: d[2] = min(d[2], d[1] + 1) (1원 동전 1개 사용)
   - 금액 3원을 만드는 경우: d[3] = min(d[3], d[2] + 1) (1원 동전 1개 사용)
   - 금액 4원을 만드는 경우: d[4] = min(d[4], d[3] + 1) (1원 동전 1개 사용)
   - 금액 5원을 만드는 경우: d[5] = min(d[5], d[4] + 1) (1원 동전 1개 사용)
   - 금액 6원을 만드는 경우: d[6] = min(d[6], d[5] + 1) (1원 동전 1개 사용)

   위의 계산을 통해 `d` 배열의 값은 다음과 같이 업데이트됩니다:
   - d[0] = 0
   - d[1] = 1
   - d[2] = 2
   - d[3] = 3
   - d[4] = 4
   - d[5] = 5
   - d[6] = 6

3. 두 번째 화폐 단위 3원을 고려합니다:
   -  i = 2일 때, array[2] = 3
   - 이제 금액 3원부터 6원까지 각각을 만들어 보면서 d 배열을 업데이트합니다.

   - 금액 3원을 만드는 경우: d[3] = min(d[3], d[3 - 3] + 1) (3원 동전 1개 사용)
   - 금액 4원을 만드는 경우: d[4] = min(d[4], d[4 - 3] + 1) (3원 동전 1개 사용)
   - 금액 5원을 만드는 경우: d[5] = min(d[5], d[5 - 3] + 1) (3원 동전 1개 사용)
   - 금액 6원을 만드는 경우: d[6] = min(d[6], d[6 - 3] + 1) (3원 동전 1개 사용)

   위의 계산을 통해 `d` 배열의 값은 다음과 같이 업데이트됩니다:
   - d[0] = 0
   - d[1] = 1
   - d[2] = 2
   - d[3] = 1
   - d[4] = 2
   - d[5] = 2
   - d[6] = 2

4. 세 번째 화폐 단위 4원을 고려합니다:
   -  i = 3일 때, array[3] = 4
   - 이제 금액 4원부터 6원까지 각각을 만들어 보면서 d 배열을 업데이트합니다.

   - 금액 4원을 만드는 경우: d[4] = min(d[4], d[4 - 4] + 1) (4원 동전 1개 사용)
   - 금액 5원을 만드는 경우: d[5] = min(d[5], d[5 - 4] + 1) (4원 동전 1개 사용)
   - 금액 6원을 만드는 경우: d[6] = min(d[6], d[6 - 4] + 1) (4원 동전 1개 사용)

   위의 계산을 통해 `d` 배열의 값은 다음과 같이 업데이트됩니다:
   - d[0] = 0
   - d[1] = 1
   - d[2] = 2
   - d[3] = 1
   - d[4] = 1
   - d[5] = 2
   - d[6] = 2

최종적으로 d[6] 값은 2로 업데이트되며, 이것은 1원, 3원, 4원 세 가지 동전을 조합하여 6원을 만드는데 필요한 최소 동전 개수를 나타냅니다.

 

따라서 d[ j ]에는 최소 동전 개수가 저장되며, 코드의 실행이 끝나면 d[m] 에는 주어진 화폐 단위로 금액 m 원을 만들기 위한 최소 동전 개수가 저장됩니다. 이 값을 출력하면 최종적인 결과가 됩니다.