[JAVA] 백준 2294번_동전 2

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

2294번: 동전 2

시간 복잡도를 고려해서 생각할 것... 재귀로 풀어서는 택도 없음 -> 저번 문제처럼 dp를 사용하자

틀린 코드 - 재귀 활용

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_2294 {
    static int n, k, tmp, min;
    static List<Integer> coin = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); k = sc.nextInt();
        while (n-- > 0) {
            tmp = sc.nextInt();
            if(tmp <= k) coin.add(tmp);
        }
        min = Integer.MAX_VALUE;
        //Collections.sort(coin, Collections.reverseOrder());
        getMinCnt(0, k, 0);
        min = min == Integer.MAX_VALUE ? -1 : min;
        System.out.println(min);
    }

    private static void getMinCnt(int idx, int rest, int cnt) {
        if(rest == 0){
            min = Math.min(min, cnt);
            return;
        }
        if(rest < 0 || idx >= coin.size()) return;
        for (int i = rest / coin.get(idx); i >= 0; i--) {
            getMinCnt(idx + 1, rest - coin.get(idx) * i, cnt + i);
        }
    }
}

dp 사용해 풀기

1. dp => MAX_VALUE - 1로 초기화 (아래 min에서 dp[k-c] 가 갱신되지 않은 경우 dp[k - c] + 1의 오버플로우 방지

2. dp[k] = min(dp[k] , dp[k - c] + 1) 로 고려

    ( " + 1" 이 되어야 하는 이유 : 동전이 2개 이상 쓰이는 경우는 k 전에서 이미 고려해서 갱신됨)

public class Main_2294 {
    static int n, k, tmp;
    static List<Integer> coin = new ArrayList<>();
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); k = sc.nextInt();
        dp = new int[k + 1];
        Arrays.fill(dp, Integer.MAX_VALUE-1);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            tmp = sc.nextInt();
            if(tmp <= k && !coin.contains(tmp)) coin.add(tmp);
        }
        Collections.sort(coin);
        for (int i = 0; i < coin.size(); i++) {
            tmp = coin.get(i);
            for (int j = tmp; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - tmp] + 1);
            }
        }
        System.out.println(dp[k] == Integer.MAX_VALUE-1 ? -1 : dp[k]);
    }
}