[백준] 2624: 동전 바꿔주기 - JAVA

26 Jun 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

dp문제.

동전으로 특정 금액을 만드는 문제였는데 동전의 개수가 정해져있어서 어려웠다.

동전 금액과 각각의 개수가 주어지는데 동전들을 이용해서 T원을 만들어야 한다.

금액에 대해 동전 몇 개를 썼을 때 경우의 수를 저장하는 dp배열을 만들었다.

동전 * 개수를 price라고 하면 점화식은 다음과 같다.

dp[k][i + 1] += dp[k - price][i];

dp[k][i+1]은 동전 (i+1)개를 썼을 때 k의 금액을 만들 수 있는 경우의 수이다.

---

메모리: 18072KB

시간: 164ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 지폐의 금액
        int K = Integer.parseInt(br.readLine()); // 동전의 가지 수

        int[][] dp = new int[T + 1][K + 1]; // dp[t][k] => 금액 t에 대해 동전 k개 까지 썼을 때 개수를 저장

        StringTokenizer st;
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken()); // 동전 하나의 금액
            int cnt = Integer.parseInt(st.nextToken()); // 개수

            dp[0][i] = 1; // 금액 0을 만들 수 있는 경우의 수 1로 초기화

            for (int j = 1; j <= cnt; j++) {
                int price = value * j; // 현재 동전을 j개 썼을 때 금액

                for (int k = price; k <= T; k++) {
                    dp[k][i + 1] += dp[k - price][i];
                }
            }

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

        System.out.println(dp[T][K]);
    }

}