[백준] 2293 동전 1 - DP JAVA

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

2293번: 동전 1

코드 설명

DP 문제입니다.

 

DP문제는 늘 그렇듯이 규칙을 찾아야합니다.

이 문제의 규칙을 찾아보겠습니다.

3 10
1
2
5

1원, 2원, 5원으로 10원을 만드는 경우의 수를 찾기위해서

각 금액을 만들기 위한 경우의 수를 찾아보았습니다.

 

1원으로 1원을 만드는경우 (1), 1

총 : 1

 

1원으로 2원을 만드는경우 (1+1), 1

2원으로 2원을 만드는경우 (2), 1

총 : 2

 

1원으로 3원을 만드는경우 (1+1+1), 1

2원으로 3원을 만드는경우 (1+2), 1

 

1원으로 4원을 만드는경우 (1+1+1+1), 1

2원으로 4원을 만드는경우 (2+2, 1+1+2), 2

총 3가지

 

1원으로 5원을 만드는경우 (1+1+1+1+1), 1가지

2원으로 5원을 만드는경우 (1+1+1+2, 1+2+2), 2가지

5원으로 5원을 만드는경우 (5) 1가지

총 4가지.

 

여기서 규칙을 찾을 수 있습니다.

DP[i] = DP[i] + DP[i - (사용하는 동전 크기)] 입니다.

2원으로 4원을 만드는경우, (4-2)2원을 만드는경우의수와 같습니다.

2원으로 5원을 만드는경우, (5-2)3원을 만드는경우의 수와 같습니다.

 

1원도 마찬가지입니다.

1원으로 4원을 만드는경우, DP[4-1] = 1 , 3원을 만드는 경우의 수와 같습니다.

 

문제에서 점화식은,

DP[i] = DP[i] + DP[i - (사용하는 동전의 크기)] 입니다.

 

DP[0] = 1 입니다. 이유는 0원에서 1원으로 갈때 1개의 코인을 사용하는 경우라고 생각하기 위함입니다.

예시로 들어보면 1원을 사용할경우,

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

이제 1원을 사용한 이후에 2원을 사용해보겠습니다.

DP[i] = DP[i] + DP[i - 2] 로 진행합니다.

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

이런식으로 DP는 곧, 각 금액을 만들 수 있는 동전의 경우의 수를 의미합니다.

 

코드

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

public class Main {
	public static int n, k;
	public static int answer = 0;
	public static int[] dp, arr;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	k = Integer.parseInt(st.nextToken());
    	
    	arr = new int[n+1];
    	dp = new int[k+1];
    	dp[0] = 1;
    	
    	for(int i=1;i<=n;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		for(int j=arr[i];j<=k;j++) {
    			dp[j] = dp[j] + dp[j-arr[i]]; 
    		}
    	}
    	System.out.println(dp[k]);
    }
    
}