SWEA 1486 - 장훈이의 높은 선반 [Java]

문제

SW Expert Academy

풀이

DP로 풀기는 했는데 백트래킹이나 BFS, 조합으로도 풀 수 있는 것 같다. N이 최대 20이라서 조합으로 푸는 게 쉬웠을지도?

import java.util.*;

public class Solution {
    private static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            System.out.println("#" + tc + " " + solution());
        }
        sc.close();
    }

    private static int solution() {
        int N = sc.nextInt();
        int B = sc.nextInt();
        int[] H = new int[N];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            H[i] = sc.nextInt();
            sum += H[i];
        }
        Arrays.sort(H);

        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int h: H) {
            for (int i = sum; i >= h; i--) {
                if (dp[i - h]) dp[i] = true;
            }
        }

        for (int i = B; i <= sum; i++) {
            if (dp[i]) return i - B;
        }

        return -1;
    }
}