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

1. 문제분석

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

문제가 이해가지 않았지만 예제풀이를 보고 해결했다.

장훈이가 너무 커서 물건을 쌓아올린 것을 직원들이 힘을 합쳐 꺼낼려고 한다.

직원들끼리 탑을 쌓아서 물건을 가져와야하고 물건과 탑의 차가 가장 적은 것을 구하면 된다.

 

필자는 조합으로 풀었다. 모든 조합의 경우의 수를 구하고 탑이 물건의 높이보다 크고 그 차가 가장 작은 값을 출력하면 된다.

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    static int min = Integer.MAX_VALUE;
    static int height;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int c = 1; c <= tc; c++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] arr = new int[size];

            for (int i = 0; i < size; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            //모든 조합 탐색
            for (int i = 1; i <= size; i++) {
                comb(arr, new boolean[size], 0, size, i);
            }

            System.out.println("#" + c + " " + min);
            min = Integer.MAX_VALUE;
        }
    }

    static void comb(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    sum += arr[i];
                }
            }
            //직원들이 탑을 쌓은 값 = sum
            if(sum >= height){
                int result = sum - height;
                min = Math.min(result, min);
            }
            return;
        }
        for (int i = start; i < n; i++) {
            visited[i] = true;
            comb(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }
}

백트래킹으로 조합을 구했다. 조합만 구할 수 있으면 쉽게 해결 가능한 문제다.

3. 마무리

보자마자 조합인 것을 알고 적용했더니 30분만에 해결했다.

문제가 어렵진 않았는데 문제내용만 보고 해석하는게 오래걸렸다.