[백준 2294 / JAVA] 동전 2

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

2294번: 동전 2

 

기존 동전에서 조금더 어려워진 버전이다.

 

동전을 입력받고 해당 동전으로 현재 상황에서 만들 수 있는 가치들을 보며 최소횟수인 경우에만 갯수를 바꿔준다.

 

        //최대 수로 채우기
        Arrays.fill(dp, 10001);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
            for (int j = coin[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
            }
        }

입력받은 동전의 가치부터 구해야하는 가치까지 보며 최소 횟수를 바꿔준다.

 

 

전체코드

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

public class Main {
    static int n, k;

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

        input = br.readLine();
        st = new StringTokenizer(input);
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        int[] coin = new int[n + 1];
        int[] dp = new int[k + 1];

        //최대 수로 채우기
        Arrays.fill(dp, 10001);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
            for (int j = coin[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
            }
        }

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

    }
}