[BOJ] 백준 2624 : 동전 바꿔주기 (java)

🧪 2624 동전 바꿔주기 

---

난이도 : 🌟 골드 5
유형 : 동적 프로그래밍 (DP)

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-1을 초과 하지 않는 것으로 가정한다.

 

입력

 

첫째 줄에는 지폐의 금액 T(0＜T ≤ 10,000), 둘째 줄에는 동전의 가지 수 k(0＜k ≤ 100), 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 pi(0＜pi ≤ T)와 개수 ni(0＜ni ≤ 1,000)가 주어진다. pi와 ni사이에는 빈칸이 하나씩 있다.

 

출력

 

첫째 줄에 동전 교환 방법의 가지 수를 출력한다. 방법이 없을 때는 0을 출력한다.

 

🧐 핵심 로직

---

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) 교환할 때까지의 경우의 수

 

💻 최종 코드 (160 ms)

---

import java.io.*;
import java.util.*;

public class Main {

    static class Coin {
        int val, cnt;

        Coin(int val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
    }

    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        int t = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        Coin[] coins = new Coin[k+1];
        int[][] dp = new int[t + 1][k + 1];

        for (int i = 1; i <= k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int val = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());

            coins[i] = new Coin(val, cnt);
        }

        for (int i = 1; i <= k; i++) {
            int val = coins[i].val;
            int cnt = coins[i].cnt;
            dp[0][i - 1] = 1;

            for (int j = 1; j <= cnt; j++) {
                for (int l = val * j; l <= t; l++) {
                    dp[l][i] += dp[l - (val * j)][i - 1];
                }
            }

            for (int j = 1; j <= t; j++) {
                dp[j][i] += dp[j][i - 1];
            }
        }

        System.out.println(dp[t][k]);
    }
}