110. 효율적인 화폐 구성

아현·2021년 7월 1일
0

Algorithm

목록 보기
111/400
  • N가지 종류의 화폐가 있다.

  • 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.

    • 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

예를 들어, 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해
3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.


  • 입력조건

    • 첫째 줄에 N, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000 )

    • 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가피는 10,000보다 작거나 같은 자연수이다.


  • 출력조건

    • 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.

    • 불가능할 때는 -1을 출력한다.



1. 타뷸레이션을 이용한 풀이



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

array = []
for i in range(n):
  array.append(int(input()))

d = [10001] * (m + 1) #dp테이블 초기화

d[0] = 0
for i in range(n):
  for j in range(array[i], m + 1):
    if d[j - array[i]] != 10001: 
      d[j] = min(d[j], d[j - array[i]] + 1)

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

  • 이 문제는 그리디에서 다루었던 거스름돈 문제와 거의 동일하다. 단지 화폐 단위에서 큰 단위가 작은 단위의 배수가 아니라는 점만 다르다.

    • 매번 가장 큰 화폐 단위부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.

  • 이번 문제는 적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다.

    • 금액 i를 만들 수 있는 최소한의 화폐 개수를 aᵢ, 화폐의 단위를 k라고 했을때 다음과 같이 점화식을 작성할 수 있다.

      • aᵢ₋ₖ(금액(i - k)를 만들 수 있는 최소한의 화폐 개수)를 만드는 방법이 존재하는 경우, aᵢ = min(aᵢ, aᵢ₋ₖ + 1 )

      • aᵢ₋ₖ를 만드는 방법이 존재하지 않는 경우, aᵢ = 10,001


  • 이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다.

    • 실제로 문제를 풀기 위해서는 가장 먼저 K의 크기만큼 리스트를 할당한다.

    • 이후에 각 인덱스를 '금액'으로 고려하여 메모이제이션을 진행한다.


  • 예를들어 N = 3, K = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 생각해보자.

    0) 초기화

    • 각 인덱스에 해당하는 값으로 10,001을 설정한다.

      • 10,001은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미이다.

        • 이보다 더 큰 수여도 상관 x
      • 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값으로 0을 설정한다.

    • 초기 리스트 값은 다음과 같다.


      1) 화폐단위: 2, 3, 5

    • 먼저 2부터 확인한다.

    • 점화식에 따라 다음과 같이 리스트가 갱신된다.

      • 예를 들어 인덱스 2의 경우 1이라는 값을 가지는데, 이는 2원짜리 화폐 하나를 이용하여 2원을 만들 수 있다는 의미이다. 즉 a₂= a₀ + 1이다.

      • 인덱스 4의 경우 2라는 값을 가지는데, 이는 2원짜리 화폐 2개를 이용하여 (2 + 2) = 4원을 만들 수 있다는 의미이다. 즉 a₄= a₂+ 1이다.

    • 10,001의 값을 그대로 가지는 경우는 2원짜리 화폐를 가지고 구성할 수 없는 금액이기 때문이다.


      **2) 화폐단위: 2, 3, 5**
    • 이어서 3을 확인한다.

    • 다음과 같이 리스트가 갱신된다.

      - 예를 들어 `a₅ = a₂+ 1`로 `2`라는 값을 가진다. 이것은 `2`원짜리 화폐 1개, `3`원짜리 화폐 1개로 `(2 + 3) = 5`원을 만들 수 있다는 의미가 된다.

      <br/>

      3) 화폐단위: 2, 3, 5

      • 이어서 5를 확인한다.

      • 다음과 같이 리스트가 갱신된다.

        • 예를 들어 a₇ = a₂+ 12라는 값을 가진다. 이는 2원짜리 화폐 1개, 5원짜리 화폐 1개로 (2 + 5) = 7원을 만들 수 있다는 의미가 된다.

          • 이전 단계에서 a₇의 값은 3이었는데, 이는 (2 + 2 + 3) = 7원으로 3개의 화폐를 사용했을 때를 나타낸 것이다.

          • 다만, 현재 단계에서 (2 + 5) = 7원을 만들면 화폐 2개만 사용해도 되므로, 더 작은 값으로 갱신된다.



2. C++ 코드

 
 
 #include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> arr;

int main(void) {
    // 정수 N, M을 입력받기
    cin >> n >> m;
    
    // N개의 화폐 단위 정보를 입력 받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
    vector<int> d(m + 1, 10001);

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

    // 계산된 결과 출력
    if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
        cout << -1 << '\n';
    }
    else {
        cout << d[m] << '\n';
    }
 
 
profile
For the sake of someone who studies computer science

0개의 댓글