[이코테] 효율적인 화폐 구성, dp - 자바

풀이

화폐의 단위의 큰 단위가 작은 단위의 배수임을 보장 받을 수 있을 경우 그리드 알고리즘을 통해 큰 단위부터 차근차근 갯수를 세면 된다.
하지만 이 문제는 입력받는 화폐의 단위가 배수임을 보장 받을 수 없어 그리디 알고리즘을 적용하지 못하고 dp를 이용해야 한다.

작은 단위부터 갯수를 적용시켜 나가며 큰 단위로 만들 수 있는 화폐의 개수를 줄여 나간다.

바로 코드를 작성해보자

코드

package 이코테.기출분석.DP;

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

public class 효율적인화폐구성 {
    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[] coins = br.lines().limit(n).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[k+1];

        // 입력받는 k의 값이 k<=10000이므로 초기값이 10001이 그대로면 -1을 출력해주기 위해 사용
        Arrays.fill(dp, 10001);
        dp[0] = 0; //0원은 0개의 화폐 필요

        for (int i = 0; i < n; i++) { // 화폐 갯수 만큼
            for (int j = coins[i]; j <= k; j++) { // 목표 금액까지의 dp 할당
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        System.out.println(dp[k] == 10001 ? -1 : dp[k]);
    }
}