[백준] 2294 동전 2 : DP [골드 5]

 

✔️ 문제 설명 (펼치기)

문제

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

입력

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

출력

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

예제 입력 1 복사

3 15
1
5
12

예제 출력 1 복사

3

 

✔️ 문제 풀이

배열 dp에 어떤 값을 넣을 것인지는 생각해냈지만, 점화식을 세우지 못 했다................

 

dp는 2차원 배열로, i원을 만들기 위한 최소 동전개수를 의미한다.

• 동전 가치의 최대는 100,000이므로 최솟값 비교를 위해 dp배열을 100,001로 초기화해준다.

1. i= 0; j=1(arr[0];

 

 

2.  i= 1; j=5(arr[1];

 

3.  i= 2; j=12(arr[2];

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] dp = new int[k+1];
        int[] arr = new int[n];
        for(int i = 0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());

        }

        Arrays.fill(dp, 100001);
        dp[0] = 0; //0원을 만들 수 있는 경우의 수는 0

        for(int i = 0; i<n; i++){
            for(int j = arr[i]; j<= k; j++){
                dp[j] = Math.min(dp[j], dp[j-arr[i]] +1);
            }
        }
        System.out.println(dp[k] == 100001? -1 : dp[k]);
    }
}