[백준] 2294 동전 2 - DP JAVA

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

2294번: 동전 2

코드설명

DP문제입니다.

 

문제에서 원하는바는, 각 금액을 만들떄 최소한의 동전을 사용해서 만들떄의 사용한 동전의 개수를 구하는 문제입니다.

 

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

DP[1] : 1

 

1원으로 2원을 만드는경우 (1+1), 1 -> 동전을 2개 사용해서 안됩니다.

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

DP[2] : 1

 

1원으로 3원을 만드는경우 (1+1+1), 1 -> 동전을 3개 사용해서 안됩니다.

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

DP[3] : 2

 

1원으로 4원을 만드는경우 (1+1+1+1), 1 ->동전 4개 사용

2원으로 4원을 만드는경우 (2+2, 1+1+2), 2 -> 동전 2개, 3개 사용

DP[4] : 2

 

위와 같이 최소의 동전의 개수의 개수를 구하는 문제입니다.

 

점화식은 다음과 같습니다.

     dp[j] = Math.min(dp[j], dp[j-arr[i]] + 1); 

 

또한 dp[0] = 0 인 이유는, 0원을 만들 수 있는 금액은 없습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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];
    	for(int i=1;i<=n;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp = new int[k+1];
    	
    	Arrays.fill(dp, 100001);
    	dp[0] = 0;
    	
    	for(int i=1;i<=n;i++) {
    		for(int j=arr[i];j<=k;j++) {
    			dp[j] = Math.min(dp[j], dp[j-arr[i]] + 1); 
    		}
    	}
    	if(dp[k] == 100001)System.out.println("-1");
    	else System.out.println(dp[k]);
    }
    
}