백준 3067[자바] java Coins

 

문제 링크: https://www.acmicpc.net/problem/3067

3067번: Coins

 

▶문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

▶입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N 가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작다고 가정해도 된다.

▶출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

▶해설

다이내믹 프로그래밍을 이용하는 문제입니다. 현재 가진 동전을 이용하여 x원을 만드는 방법의 개수 찾기입니다. 그림을 그려보면 쉽게 이해할 수 있습니다. 

 

예로 동전으로 5원 7원이 있고, 22원을 만드는 방법의 수를 알아보겠습니다.

 

1. 동전1 즉 5원으로 만들 수 있는 금액들은 5의 배수입니다. 5, 10, 15, 20

2. 동전2 즉 7원으로 만들 수 있는 금액은 동전 2가 만들 수 있는 경우의 수와 동전 1로 만들어진 경우의 수를 더하는 것입니다.

 

그림으로 보겠습니다. 

동전 1 5원으로 만들 수 있는 금액은 자신의 금액입니다. 

 

동전 2는 5원으로 만들 수 있는 금액의 수 + 자신의 금액입니다. 

 

 

하지만 이때 17과 22의 경우를 주목할 필요가 있습니다. 5원으로 만들 수 있는 금액 + 7원으로 만들 수 있는 금액을 합치면 만들 수 있습니다. 따라서 17은 아래와 같이 표시됩니다. 

 

즉 이전 동전이 만든 개수 + (구하려는 금액 - 현재 동전의 값)의 개수를 구하면 정답이 됩니다 따라서 아래와 같이 점화식이 됩니다. 이때 주의할 점은 현재 동전의 금액보다 작은 것은 이전의 동전의 값을 그대로 가져와야 합니다. 

private static void makeAnswer() {
    for(int j=1; j<=n; j++){
        for(int q=1; q<=target; q++){
            if(q-arr[j]<0){ // 구하려는 금액 - 현재 동전의 값<0 이라면 이전 동전의 값을 가져온다.
                dp[j][q]=dp[j-1][q];
                continue;
            }
            dp[j][q] += dp[j-1][q]+dp[j][q-arr[j]];
        }
    }
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.time.LocalDate;
import java.util.*;
import java.lang.*;



public class Main {

    static int t,n;
    static int target;
    static int[] arr;
    static int [][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<t; i++){
            n = Integer.parseInt(br.readLine());
            arr = new int[n+1];
            dp = new int[n+1][10001];
            String[] s = br.readLine().split(" ");
            for(int j=1; j<=n; j++){
                arr[j] = Integer.parseInt(s[j-1]);
                dp[j][Integer.parseInt(s[j-1])]++;
            }
            target = Integer.parseInt(br.readLine());

            makeAnswer();

            sb.append(dp[n][target]).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void makeAnswer() {
        for(int j=1; j<=n; j++){
            for(int q=1; q<=target; q++){
                if(q-arr[j]<0){
                    dp[j][q]=dp[j-1][q];
                    continue;
                }
                dp[j][q] += dp[j-1][q]+dp[j][q-arr[j]];
            }
        }
    }
}