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

문제 출처: SW Expert Academy

SW Expert Academy

: 주어진 점원들의 키를 합한 값 중에서 선반의 높이를 넘으면서 가장 작은 값을 구해야한다.

: 합할 수 있는 점원들의 수가 제한되어 있지 않기 때문에 부분집합 개념을 사용해서 풀이했다.

: 또한 원소 전체를 탐색하지 않았어도 그 키를 합한 값이 B를 넘으면 return 시킬 수 있도록 powerset() 메서드 안에서 if문을 사용하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int[] height;
    static int N = 0, B = 0;
    public static void main(String[] args) throws NumberFormatException, IOException {
        // 테스트 케이스 수를 입력 받고
        int T = Integer.parseInt(br.readLine());
         
        // 테스트 케이스 수만큼 반복하며
        for(int tc = 1; tc <= T; tc++) {
            // 점원의 수와 선반의 높이를 입력받고
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
             
             
            // 점원들의 수만큼 각각의 키를 입력받는다.
            height = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++) {
                height[i] = Integer.parseInt(st.nextToken());
            }
            minHeight = Integer.MAX_VALUE;
            powerset(0,0);
            sb.append(String.format("#%d %d\n", tc, (minHeight - B)));
        }
        System.out.println(sb);
    }
    static int minHeight = Integer.MAX_VALUE;
    private static void powerset(int idx, int total) {
        if(total >= B) {
            minHeight = total < minHeight ? total : minHeight;
            return;
        }
        if(idx == N ) {
            // 부분집합으로 만들 수 있는 키 중에서 선반의 높이 이상이면서 
            // 그 중에서 가장 작은 높이를 구한다.
            if(total >= B) minHeight = total < minHeight ? total : minHeight; 
            return;
        }
         
        powerset(idx+1, total+height[idx]);
        powerset(idx+1, total);
    }
}