[백준 #3067] Coins - JAVA(자바)

문제

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

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

해설

Dynamic Programming의knapsack 문제이다. dp 문제는 보통 1) dp 배열 정의, 2) 초기화, 3) 점화식 세 단계를 갖는다. 

 

1) dp 배열 정의:

dp[n][m]: n번째 동전까지 모두 사용했을 때 금액 m을 만들 수 있는 방법의 수

 

2) 초기화

dp[n][0] = 1

보통 dp 문제는  1) dp 배열 정의, 2) 초기화, 3) 점화식  이 단계를 가져서 문제 조건에 따라 직접 경우를 따져보면 초기화 값을 쉽게 찾는데 이 문제에서는 점화식을 먼저 정의하고 이때 필요한 초깃값을 구했더니 이런 식이 나왔다.

 

3) 점화식

dp[n][m] = dp[n-1][m] + (m-coin[n] >= 0 ? dp[n][m-coin[n]] : 0) // coin[n]: n번째 동전의 금액

예를 들어 동전 1,2 가 있을 때 2번째 동전까지 모두 사용했을 때(1원, 2원)를 생각해 보자.

dp[2][5] = dp[1][5] + dp[2][5-2] 이 되는데 dp[1][5] 는 1원만 사용했을 때 5원을 만든 방법의 수 (1 = {1,1,1,1,1}) 이고 dp[2][5-2] 은 1원과 2원 모두 사용했을 때 3원을 만드는 방법의 수 (2 = {1,1,1},{1,2}) 를 나타낸다. 이 조합들에 2원을 사용하면 5원을 만들 수 있다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int i = 1; i <= n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            int m = Integer.parseInt(br.readLine());
            int[][] dp = new int[n+1][m+1]; // dp[n][m]: n번째 동전까지 모두 사용했을 때 금액 m을 만들 수 있는 모든 방법의 수
            for(int i = 1; i <= n; i++){
                dp[i][0] = 1;
                for(int j = 1; j <= m; j++){
                    dp[i][j] = dp[i-1][j];
                    if(j - arr[i] >= 0) {
                        dp[i][j] += dp[i][j-arr[i]];
                    }
                }
            }
            sb.append(dp[n][m]).append("\n");
        }
        System.out.print(sb);
    }
}