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

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

2624번: 동전 바꿔주기

 

🐢 설명

DP문제이다. 동전 문제처럼 접근하면 될거같지만 조금 다른점이 있는데 금액별 동전들에 대해 개수제한이 있다. 따라서 각 동전별로 개수 내에서 M원까지의 금액에 대해 갱신을 해줘야한다.

 

개수제한이 없다면 1 ~ M원까지 모든 동전들을 비교하면 되겠지만 개수를 확인해줘야 하므로 2차원 배열을 만들어서 동전번호 별로 DP를 괸리하도록 하자.

 

먼저 A원동전이 A원을 나타내는 방법은 1가지이므로 DP[Aidx][0] = 1로, 모든 동전들에 대해서 똑같이 해준다. 이 후 가격이 낮은 동전부터 DP배열을 채우는데 중요한 점은 개수를 달리해보면서 DP를 채워야 하므로 A원 이하의 금액에 대해서도 확인을 해줘야 한다.

 

따라서 dp[ N번 동전 ][ 현재금액 ] += dp[ N-1번 동전 ][ 현재금액 - ( N번 동전 금액 * 0개 ~ N번 동전 개수 ) ] 와 같은 식이 나오게 된다.

 

🐢코드

package Gold이상문제_정리;

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

public class 동전바꿔주기_2624 {
    static int M, N;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        M = Integer.parseInt(br.readLine());
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1][M + 1];

        ArrayList<int[]> coins = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int coin = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            coins.add(new int[]{coin, cnt});
        }
        coins.add(new int[]{0, 0});

        coins.sort(Comparator.comparingInt(c -> c[0]));
        for (int i = 0; i <= N; i++) {
            dp[i][0] = 1;
        }
        for (int cidx = 1; cidx <= N; cidx++) {
            int[] coin = coins.get(cidx);
            int cost = coin[0];
            int coinCnt = coin[1];
            for (int money = 1; money <= M; money++) {
                for (int i = 0; i <= coinCnt; i++) {
                    if (money - (cost * i) < 0) break;
                    dp[cidx][money] += dp[cidx - 1][money - (cost * i)];
                }
            }
        }

        System.out.println(dp[N][M]);
    }
}