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

 

 

 

문제 출저

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

2624번: 동전 바꿔주기

 

 

 

문제 풀이

금액 T가 주어집니다. 동전의 금액과 갯수가 K개 주어집니다. 금액 T를 거슬러줄 수 있는 방법을 구해야 합니다. 

 

예제)

20

3

5 3

10 2

1 5

 

금액 20원과 동전의 금액과 갯수가 3개 주어집니다. 

동전의 금액과 갯수는 각각 5원짜리 3개, 10원짜리 2개, 1원짜리 5개입니다. 

 

 

 

DP를 이용해 풀었습니다.

냅색 알고리즘이 생각나 이를 응용해 풀었습니다. 

 

int[][] dp = new int[k+1][t+1]로 선언합니다. 이 2차원 int 배열인 dp에 경우의 수를 저장합니다.

세로값은 동전을 의미하며 가로는 금액을 의미합니다. 

세로값의 동전 1은 (5,3) 2는 (10,2) ... 를 의미합니다. 

 

주어진 동전 금액과 갯수로 사용할 수 있는 금액을 확인합니다.

 

동전1부터 로직을 처리합니다. 동전 1은 (5, 3) 입니다.

5원짜리 3개로 만들 수 있는 금액은 5원 10원 15원 입니다.

dp[1][5], dp[1][10], dp[1][15]에 1을 더합니다. 

 

새로운 동전을 처리하기 전에 반복문을 돌아 전에 경우의 수를 업데이트합니다.

즉, 금액 전체인 1원 부터 목표 금액인 20원까지 반복문을 돌아 dp[i][l] = dp[i-1][l]로 업데이트 합니다. 

 

다음 동전 2인 (10, 2)를 처리합니다.

10원짜리 2개로 만들 수 있는 금액은 10원, 20원 입니다.

dp[2][10], dp[2][20]에 1을 더합니다.

그 다음 동전 1에 10원, 20원을 더했을 때 만들 수 있는 금액에 +1을 합니다.

dp[2][l] += dp[1][l - 10] 이런 식으로 됩니다. 

 

이 과정을 반복하면 dp[k][t]에 정답이 구해집니다. 

배낭 알고리즘, 냅색 알고리즘을 학습하면 문제를 풀 때 도움이 될 거 같습니다. 

 

 

소스코드

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

/*
동전 바꿔주기
https://www.acmicpc.net/problem/2624

돈 도달하기까지 동전이 몇 개 필요한지 알아야 한다.

4% 틀렸습니다.
점화식을 다시 세워서 풀었다.
 */

public class Main {

    static int t; // 지폐의 금액
    static int k; // 동전의 가지 수
    static int[] moneys;
    static int[] counts;
    static int[][] dp;

    static int answer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

        moneys = new int[k];
        counts = new int[k];

        for (int i = 0; i < k; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            moneys[i] = Integer.parseInt(st.nextToken());
            counts[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[k + 1][t + 1];

        for (int i = 1; i < k + 1; i++) {

            int money = moneys[i - 1];
            int count = counts[i - 1];

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

            for (int j = 1; j < count + 1; j++) {
                int nowMoney = money * j;

                if(nowMoney > t) continue;
                dp[i][nowMoney] += 1;

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

            }

            // printDp();

        }

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



    }

    public static void printDp() {
        for (int i = 0; i < k + 1; i++) {
            for (int j = 0; j < t + 1; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }


}