백준 2624번 동전 바꿔주기 :: 마이구미

이 글은 백준 알고리즘 문제 2624번 "동전 바꿔주기" 를 풀이한다.

풀이 방법으로는 동적계획법을 통해 진행된다.

문제 링크 - https://www.acmicpc.net/problem/2624

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10×2 
• 20 = 10×1 + 5×2 
• 20 = 10×1 + 5×1 + 1×5 
• 20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법 의 수는 231을 초과하지 않는 것으로 가정한다.

동전 관련 문제들을 해결할 때, 대부분 비슷한 방식으로 문제를 해결했다.

그 방법은 각 동전에 대한 경우의 수를 누적해나가는 방식을 활용했다. (다른 점은 동전에 따른 개수가 생겼다.)

여기서도 흡사한 방식으로 점화식을 만들어보자.

dp[n][k] = n원을 동전 k개까지 교환할 때까지의 경우의 수

먼저 1원 - 5개 , 5원- 3개가 주어졌을 경우 6원의 경우의 수를 구하는 방법을 생각해보자.

5원짜리만으로는 6원을 만들 수 없기 때문에, 이전 동전인 1원짜리를 활용해야한다.

단순하게 5원 + 1원을 통해 구할 수 있고, 7원 = 5원 + 2원, 8원 = 5원 + 3원 .....등등과 같이 구할 수 있다.

주어지는 동전의 가지 수에는 금액과 개수가 주어진다.

개수가 존재하기 때문에, 개수를 고려해준 점화식은 다음과 같다.

ex) dp[6][2] = dp[6][2] + dp[6 - 5][1]

dp[n][k] = dp[n][k] + dp[n - (v * c)][k - 1] // v = 사용되는 동전의 금액, c = 동전 개수(1 ~ n)
=> n원을 k개까지의 경우의 수 + n - v * c(사용되는 동전) 원을 이전 동전까지(k-1) 교환할 때까지의 경우의 수 

관련 동전 문제를 접한 후 풀어보면 더 좋을 것이다. (관련 문제 링크)

동적계획법 관련 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/graph

private void solve() {
    int m = sc.nextInt();
    int n = sc.nextInt();
    Coin[] coins = new Coin[10001];
    int[][] dp = new int[10001][101];
 
    // dp[n][k] = n원일 때 동전 k개까지 사용했을 때의 경우의 수
    // dp[n][k] = dp[n][k] + dp[n - v * c][k - 1]
 
    for (int i = 1; i <= n; i++) {
        int v = sc.nextInt();
        int c = sc.nextInt();
 
        coins[i] = new Coin(v, c);
    }
 
    for (int i = 1; i <= n; i++) {
        int v = coins[i].value;
        int c = coins[i].count;
        dp[0][i - 1] = 1;
 
        for (int j = 1; j <= c; j++) {
 
            for (int k = v * j; k <= m; k++) {
                dp[k][i] += dp[k - (v * j)][i - 1];
            }
 
        }
 
        for (int j = 1; j <= m; j++) {
            dp[j][i] += dp[j][i - 1];
        }
    }
    System.out.println(dp[m][n]);
}
 
class Coin {
 
    int value = 0;
    int count = 0;
 
    Coin(int value, int count) {
        this.value = value;
        this.count = count;
    }
 
}