[ 백준 6148번 ] Bookshelf 2

1. 문제

6148번: Bookshelf 2

 

2. 풀이

문제를 간단하게 요약하면 다음과 같다. John이 가지고 있는 소들을 책장 높이 이상으로 쌓았을 때, 책장과 소들의 높이의 차이가 최소가 되는 경우를 구하라는 것이다. 

 

조건들은 아래와 같다.

• N ≤ 20 (N은 소의 총 숫자)
• H_i ≤ 1,000,000 (소의 높이)
• 1 ≤ B ≤ S (B = 책장 높이, S = 전체 소 높이의 합

 

조건들로부터 유추할 수 있는 점은 책장 높이 이상으로 소를 쌓을 수 있는 경우가 있다는 것이다. 또한 소가 전체 20마리 이하로 제공되므로, 백트래킹을 이용해서 최적의 높이를 탐색할 수 있게 된다. 즉 요소를 반복해서 사용할 수 없는 조합의 문제와 동일하며, 백트래킹을 통해 경우의 수를 만들어내고 해당 경우의 수가 최적의 높이인지를 판단하면 된다.

 

하지만 현재 이 문제는 input의 크기가 작다는 점에서 Brute force 형식으로 풀이하였다. 다만 백트래킹의 기본이 되는 재귀를 사용하여 브루트 포스를 구현하였으니 자세한 내용은 코드를 참고하자.

 

3. 소스코드

public class Main {

    static int N, H, ans = Integer.MAX_VALUE;
    static int[] height;

    static void backtracking(int start, int tot) {
        if (tot >= H) {
            ans = Math.min(ans, tot - H);
            return;
        }

        for (int i = start; i < N; i++) {
            backtracking(i + 1, tot + height[i]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        height = new int[N];
        for (int i = 0; i < N; i++) {
            height[i] = Integer.parseInt(br.readLine());
        }

        backtracking(0, 0);

        bw.write(ans + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code