백준 2294 동전 2 자바(java)

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

2294번: 동전 2

 

풀이 방법

다이나믹 프로그래밍을 사용한다.

 

1. k+1 길이의 dp 배열을 생성하고 100001 로 초기화한다.

    1~k 까지의 가치를 인덱스로 하여 각 가치를 만들 수 있는 동전의 최소 개수를 저장한다.

    즉, dp[5] 는 가치 5를 만들기 위해 필요한 동전의 최소 개수가 된다.

    동전의 가치 입력 범위가 100000 이므로 +1 을 하여 초기화한다.

    주의, dp[0] = 0 이어야 한다!

 

2. 입력 받은 동전 배열을 차례대로 순회하면서 dp 값을 갱신해나간다.

    i번 동전으로 dp[j] 를 구할 때 점화식은 dp[j] = min(dp[j], dp[j - i번 동전의 가치] + 1) 이다.

    현재 dp 값과 i번 동전을 추가하여 가치를 만들었을 때의 개수를 비교하는 것이다.

 

dp 값 갱신을 완료한 후 dp[k] 값이 처음 초기화했던 100001 라면 k의 가치를 만들 수 없다는 것이므로 -1을 출력하면 된다!

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        int[] coins = new int[n];
        for(int i=0; i<n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[k+1];
        for(int i=1; i<k+1; i++) {
            dp[i] = 100001;
        }

        for(int i=0; i<n; i++) {
            // j의 가치를 만들 수 있는 동전 최소 개수 구하기
            for(int j=coins[i]; j<=k; j++) {
                dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
            }
        }

        if(dp[k] == 100001) {
            System.out.println(-1);
        } else {
            System.out.println(dp[k]);
        }
    }
}