[백준 2294] 동전2 / 자바 / dp

문제         

레벨: G5
알고리즘: dp(업데이트 기준 1 개)
풀이시간: 1시간
힌트 참조 유무: 무

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

1 번째 시도   

• 동전1과는 다르게 dp배열에 만들 수 있는 가지수가 들어가는 것이 아닌 최소한의 동전 개수가 들어가야 한다.
• 동전1과 마찬가지로 업데이트 기준은 1가지이다. 
• dp는 점화식을 세우는 것이 시작이자 제일 중요하다
•  arr[j] = Math.min(arr[j], arr[j - coin[i]] + 1);

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int[] arr = new int[K + 1];
        int[] coin = new int[N];
        for (int i = 0; i < N; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(arr, K + 1); // 초기화를 충분히 큰 값으로
        arr[0] = 0; // 0원을 만들기 위해 필요한 동전의 수는 0

        for (int i = 0; i < N; i++) {
            for (int j = coin[i]; j <= K; j++) {
                arr[j] = Math.min(arr[j], arr[j - coin[i]] + 1);
            }
        }

        if (arr[K] == K + 1) {
            System.out.println(-1); // 목표 금액을 만들 수 없는 경우
        } else {
            System.out.println(arr[K]);
        }
    }
}