[SWEA] 장훈이의 높은 선반

➊ 서론

① 문제

서점에는 높이가 B인 선반이 하나 있는데 장훈이는 키가 매우 크기 때문에, 선반 위의 물건을 자유롭게 사용할 수 있다.

어느 날 장훈이는 자리를 비웠고, 이 서점에 있는 N명의 점원들이 장훈이가 선반 위에 올려놓은 물건을 사용해야 하는 일이 생겼다.

각 점원의 키는 Hi로 나타나는데, 점원들은 탑을 쌓아서 선반 위의 물건을 사용하기로 하였다.

점원들이 쌓는 탑은 점원 1명 이상으로 이루어져 있다.

탑의 높이는 점원이 1명일 경우 그 점원의 키와 같고, 2명 이상일 경우 탑을 만든 모든 점원의 키의 합과 같다.

탑의 높이가 B 이상인 경우 선반 위의 물건을 사용할 수 있는데 탑의 높이가 높을수록 더 위험하므로 높이가 B 이상인 탑 중에서 높이가 가장 낮은 탑을 알아내려고 한다.

② 문제를 이해해보자!

선반의 높이 B와 점원 N명의 키가 주어진다.
점원들을 탑 쌓아 선반의 높이 B를 넘어야 한다!
탑을 쌓는 여러 경우의 수 중 가장 높이가 낮아야 한다.

➋ 풀이 과정

① 부분 집합

Top을 이루는 점원들의 조합을 구해야 하는데
몇 명을 뽑아야 하는지 정해져 있지 않다!
nC1부터 nCn 까지의 모든 조합을 생각해야 하기 때문에
부분 집합의 아이디어로 접근하였다.

위 그림과 같이 각 사람을 선택할 수도 있고, 선택하지 않을 수도 있다.
N명에 대하여 [ 선택하는 경우 / 선택하지 않는 경우 ] 2가지가 존재하므로

모든 조합을 구하는 시간복잡도는 O(2^N)이 된다.

그런데 문제에서 N의 범위는 (1 ≤ N ≤ 20) 이었기 때문에
최악의 경우 2^20 = 1,048,576번 연산을 수행하기 되며,
자바는 1초에 1억 번의 연산을 수행하기 때문에 충분히 가능하다고 생각했다!

② 재귀

makeTop 함수를 재귀적으로 호출하며 부분 집합을 생성하였다.
이때 인수로 현재 Top 의 높이를 전달해주었고,
Top 의 높이가 선반의 높이 이상일 경우 재귀를 종료하도록 하였다.

또한, 현재 몇 번째 점원의 키를 가리키고 있는지에 대한 index 를 인수로 전달해주었다.
마지막 점원의 키까지 가리키고 나면 또 재귀를 종료하도록 하였다.

따라서 재귀의 종료 조건은 두 가지이다.

위 종료 조건에 해당하지 않는다면
자기 자신 함수를 재귀적으로 호출하도록 하였다.

이때 index 가 가리키는 현재 점원의 키를 Top 에 포함할 경우와
포함하지 않을 경우로 나누어서 2번 재귀적으로 호출하였다.

➌ 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer tokens;
    private static StringBuilder sb = new StringBuilder();
 
    private static int N; // 점원 수
    private static int B; // 선반 높이
 
    private static int[] person; // 점원들의 키 배열
    private static int minTop; // 출력하고자 하는 답!
 
 	// Top을 이루는 모든 조합 생성
    private static void makeTop(int index, int top) {
    	// 종료 조건 ➊
        if (top >= B) {
            if (minTop > top) {
                minTop = top;
            }
            return;
        }
 		
        // 종료 조건 ➋
        if (index == N) {
            return;
        }
 		
        // 현재 점원을 Top에 포함시키는 경우
        makeTop(index + 1, top + person[index]);
        // 현재 점원을 Top에 포함시키는 않는 경우
        makeTop(index + 1, top);
    }
 
 	// 입력
    private static void init() throws IOException {
        tokens = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(tokens.nextToken());
        B = Integer.parseInt(tokens.nextToken());
 
        tokens = new StringTokenizer(br.readLine());
        person = new int[N];
        minTop = Integer.MAX_VALUE;
 
        for (int i = 0; i < N; i++) {
            person[i] = Integer.parseInt(tokens.nextToken());
        }
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        int T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            init();
            makeTop(0, 0);
            sb.append("#").append(t).append(" ").append(minTop - B).append("\n");
        }
 
        System.out.println(sb);
    }
 
}