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

https://www.acmicpc.net/problem/2624

728x90

---

메모리: 18,796 KB , 시간: 164 ms

사용 알고리즘: 다이나믹 프로그래밍

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        int[][] coin = new int[k][2];

        long[][] dp = new long[T + 1][k];
        Arrays.fill(dp[0], 1);

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            coin[i][0] = Integer.parseInt(st.nextToken());
            coin[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(coin, (o1, o2) -> o1[0] - o2[0]);

        // 가장 작은 금액의 동전의 경우는 미리 구해놓기
        int p = coin[0][0], c = 1;
        while(c <= coin[0][1] && p * c <= T) {
            dp[p * c][0]++;
            c++;
        }

        for (int i = 1; i < k; i++) { // 동전 순서대로 확인

            // 현재 동전의 금액
            p = coin[i][0];

            for (int j = 1; j <= T; j++) { // 만들고자 하는 금액
                c = 0;
                while((c <= coin[i][1]) && (j - p * c >= 0)) {
                    dp[j][i] += dp[j - p * c][i - 1];
                    c++;
                }
            }
        }

        System.out.println(dp[T][k - 1]);
    }
}