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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

SW Expert Academy

생각

N이 최대 20까지이므로 최대 2^20 연산이 필요합니다. 따라서 부분집합으로 문제를 풀 수 있습니다. 공집합일때는 제외하고 1부터 N개를 뽑았을때의 부분집합을 만들어줍니다. 만들어진 부분집합의 총 합과 탑 높이의 차가 가장 적은것을 찾아주면 됩니다.

 

재귀로 부분집합을 구현했는데 비트마스킹으로 구현하는것도 연습해야겠습니다

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
2^20 부분집합 가능
*/
public class Solution {
    static int N;
    static int B;
    static int[] height;
    static boolean[] isSelected;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;
        int TC = Integer.parseInt(br.readLine());
        for (int t = 1; t <= TC; t++) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
             
            height = new int[N];
            isSelected = new boolean[N];
             
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < N; i++) {
                height[i] = Integer.parseInt(st.nextToken());
            }
            ans = Integer.MAX_VALUE;
            for (int i = 1; i <= N; i++) {
                subset(0, i);
            }
            sb.append("#").append(t).append(" ").append(ans).append("\n");
        }// end of test case
         
        System.out.print(sb);
 
    }
    private static void subset(int cnt, int pick) {
        if(cnt == pick) {
            int total = 0;
            for (int i = 0; i < N; i++) {
                if(isSelected[i]) {
                    total += height[i];
                }
            }
            if(total >= B) {
                ans = Math.min(ans, total-B);
            }
            return;
        }
        isSelected[cnt] = true;
        subset(cnt+1, pick);
        isSelected[cnt] = false;
        subset(cnt+1, pick);
    }
 
}