[백준 9084] 동전

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

9084번: 동전

 

배낭 문제 중 하나.

이차원 배열을 만들어 계산하였다.

가로는 선택할 수 있는 동전의 가치, 세로줄은 총 금액으로 하여 가짓수를 채우는 표를 만들어 보면 다음과 같다.

 

	1	2	3	4	5	10	20
1원	1	1	1	1	1	1	1
5원	1	1	1	1	2	3	5
10원	1	1	1	1	2	4	9

 

 

아래로 갈 수록 선택할 수 있는 동전의 개수가 많아진다(5원 행의 경우에서는 1원, 5원 둘 다 선택할 수 있음)

[5원][20]의 경우를 생각해 보면, 

 

1) 5원*4 

2) 5월*3 + 1원*5

3) 5원*2 + 1원*10

4) 5원*1 + 1원*15

5) 5원*0 + 1원*20

위와 같이 5가지로 나눌 수 있다.

이 때 1,2,3,4번째 경우는 [5원][15]의 가짓수와 똑같다고 할 수 있다. 

([5원][15]에서 동전을 선택한 상태에서 5원을 하나 더 얹어주었다고 생각하면 됨.)

그리고 마지막 5번째 경우는 [1원][20]의 경우이므로, 

[5원][20] = [5원][15] + [1원][20]

이라는 점화식을 만들 수 있다. (배낭 문제 기본 점화식.)

 

 

주의 ) 

1) Index out 예외를 주의해야 함.

2) [row][0]의 값을 1로 설정해야 한다.  -> 설정하지 않으면 당연히 모든 값이 0이 됨.

  

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int coin[] = new int[N + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i < N + 1; i++) {
                coin[i] = Integer.parseInt(st.nextToken());
            }
            int M = Integer.parseInt(br.readLine());

            int count[][] = new int[N + 1][M + 1];
            for (int i = 1; i < N + 1; i++) {
                count[i][0] = 1;
                for (int j = 1; j < M + 1; j++) {
                    count[i][j] += count[i - 1][j];
                    if (j - coin[i] >= 0) {
                        count[i][j] += count[i][j - coin[i]];
                    }
                }
            }
            System.out.println(count[N][M]);
        }
    }
}