[백준] 2294 동전 2 - JAVA

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

2294번: 동전 2

 

[풀이] 

• DP를 사용해서 접근 
• dp[i] : i원을 만드는데 필요한 최소 동전의 갯수
• n가지 종류의 동전 coin[j] 가 주어졌을 때, coin[] 금액만큼 제외한 dp 값 +1 중 최솟값을 찾는다. 
• 점화식 : dp[i] = min(dp[i], dp[i-coin[j]] +1)
• 단, 최솟값을 찾기 위해서 dp 초기값을 큰 정수값으로 초기화 시켜줘야하는데 Integer.MAX_VALUE로 하면 안된다! 
  dp[i-coin[j]] + 1 과정 때문에. k의 범위가 10000 까지이므로 10001 로 초기화 
• 마지막에 dp값이 10001 이라면 불가능한 경우이므로 -1 출력. 

---

 

[구현 과정]

• dp[] : 각 금액을 만드는데 필요한 최소 동전의 갯수 
• coin[] : n가지 종류의 동전 저장 

 

1. n가지 종류의 동전을 입력받아 coin 배열에 저장 

 

2. 최솟값을 찾아 dp배열에 저장해야하기 때문에, dp 배열을 10001로 초기화 한 후, dp[0] = 0 . 

 

3. 현재 금액이 각 coin 값 이상일 경우, dp[i-coin[j]] + 1 과 현재 저장되어 있는 값을 비교해 최솟값을 찾는다.

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

 

4. 모든 dp 값을 채웠을 때 dp[k] 값이 10001이라면, 동전으로 만들 수 없는 금액이므로 -1을 출력한다.

 

5. 그렇지 않다면 dp[k] 값을 그대로 출력한다. 

 

 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		st= new StringTokenizer(br.readLine(), " ");
		int n= Integer.parseInt(st.nextToken());
		int k= Integer.parseInt(st.nextToken()); 
		
		int coin[] = new int[n]; 
 		int dp[] = new int[k+1]; 
 		
 		for(int i=0; i<n; i++) {
 			coin[i] = Integer.parseInt(br.readLine()); 
 		}
		
 		Arrays.fill(dp,10001);
 		dp[0] =0; 
 		
 		for(int i=0; i<=k; i++) {
 			for(int j=0; j<n; j++) {
 				if(coin[j] <= i) {
 					dp[i] = Math.min(dp[i-coin[j]] +1, dp[i]); 
 				}
 			}
 		}

 		System.out.println((dp[k] == 10001)? -1 : dp[k]);
	}//end of main
}//end of class