[백준] 9084 동전 - DP JAVA

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

9084번: 동전

코드설명

DP를 활용한 동전문제입니다.

 

이전에 비슷한 문제 2293 을 풀어본적있어서 해당 풀이를 통해 함께 설명해보겠습니다.

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

총 : 2

 

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가지.

 

위의 4가지 경우를 살펴보았을때 규칙성을 확인할 수 있습니다.

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

 

이때, 쉽게 이해해보면,

DP[1] : 1원을 만드는데 가능한 경우의 수

DP[2] : 2원을 만드는데 가능한 경우의 수

DP[3] : 3원을 만드는데 가능한 경우의 수

DP[4] : 4원을 만드는데 가능한 경우의 수

DP[5] : 5원을 만드는데 가능한 경우의 수

 

위의 처럼 이해할 수 있습니다.

먼저 동전이 1일때의 DP를 모두 구합니다.

DP[0] ~ DP[M] 까지 모두 구해졌다고 가정해봅니다.

이떄, 동전 1으로 만들수 있는 경우의 수는 모두 1일 것입니다. DP[0] ~ DP[M] = 1 ( 모두 1일것)

 

이제 동전이 2일떄의 DP를 구해봅니다.

만약 DP[2] = DP[2] + DP[2 - 2]; 일것입니다.

DP[3] = DP[3] + DP[3-2]; 이유는 이전에 구한 1원의 경우에 수에서 본인의 금액만큼 더해주면 해당 값의 경우의 수와 똑같을 것입니다.

 

코드

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

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