백준 2293 동전 1 Java

동적 프로그래밍 문제인 동전 1이다.

 

dp[K]에는 가치가 K일 때 경우의 수를 저장한다.

 

N만큼 주어진 동전의 가치 별로

K를 만드는 경우의 수를 구해서

dp배열에 누적합을 시켜준다.

 

동전 문제의 특징인 누적합을 시켜준다는 포인트를 생각해서

점화식을 생각해보면

for(int i=1; i<=n; i++) {
    for(int j=coins[i]; j<=k; j++) {
        dp[j] += dp[j-coins[i]];
    } 
}

이처럼 점화식이 나올 수 있다.

 

dp[0]에는 아예 동전을 안사용하는 경우가 있으므로

dp[0] = 1이다.

 

예제의 경우에 dp 배열을 살펴보면

 

coins[1] = 1

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

coins[2] = 2

1	2	3	4	5	6	7	8	9	10
1	2	2	3	3	4	4	5	5	6

coins[3] = 5

1	2	3	4	5	6	7	8	9	10
1	2	2	3	4	5	6	7	8	10

 

이처럼 동전의 가치별로 경우의 수가 더해진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q2293 {
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] coins = new int[n+1];
        int[] dp = new int[k+1];
        dp[0] = 1;
        for(int i=1; i<=n; i++) {
            coins[i] = Integer.parseInt(reader.readLine());
        }
        for(int i=1; i<=n; i++) {
            for(int j=coins[i]; j<=k; j++) {
                    dp[j] += dp[j-coins[i]];
            }
        }
        System.out.println(dp[k]);
    }
 
}