• 백준 2624번 동전 바꿔주기 :: 마이구미
    알고리즘 풀이/동적계획법 2017. 11. 21. 20:18
    반응형

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    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;
        }
     
    }
    cs


    반응형

    댓글

Designed by Tistory.