[Java] [백준 2294][DP] 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

---

문제 풀이 (DP)

 

이 문제는 전형적인 DP문제이다.

 

모든 경우를 확인해야 되는데 확인할때  dp에 업데이트 시켜주면서 최소값을 계속 비교하면 된다.

 

Dp의 점화식은 Math.min([dp[j] , dp[j-c[i]+1]) 이다.

 

이 문제를 순서대로 풀어보자면 다음과 같은 방식으로 진행된다.

 

[0, 1, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 10001, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10001, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10001, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10001, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 10001, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 10001, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 10001]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

------ 여기까지는 동전 1이 최소값이니까 1씩 증가하면서 dp에 저장된다.

[0, 1, 2, 3, 4, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 11, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 12, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 13, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 14, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 15]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 3]

-----여기까지는 동전 5가 있으니까 5원이 1이되고 6은 (5원+1원)이니까 2가된다. 10이되면 (5원 2개)니까 2가되고 다시 3..4 

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 5, 6, 3]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 6, 3]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 3, 3]

[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 3, 3]

 

결국 가치의 합 K가 되는 것은 마지막 index값이다. 만약 10001이면 한번도 이곳에 오지 못한거니까 -1을 출력한다.

package com.Boj.Day2;

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

public class BOJ_2294 {
	static int n,k;
    static int c[];
    static int dp[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        c = new int[n];
        dp = new int[k+1];
        for(int i=0; i<n; i++) {
            c[i] = Integer.parseInt(br.readLine());
        }
        // 초기값 100001로 채우기
        Arrays.fill(dp, 10001);
        
        // 처음은 0이니까 
        dp[0]=0;
        for(int i=0;i<n;i++) {
        	for(int j=c[i];j<=k;j++) {
            	// 점화식에 맞게 확인하면서 최소값으로 업데이트
        		dp[j]=Math.min(dp[j], dp[j-c[i]]+1);
        		System.out.println(Arrays.toString(dp));
        	}
        }
        
        if(dp[k] ==10001) {
        	System.out.println(-1);
        }else {
        	System.out.println(dp[k]);
        }

	}

}