[알고리즘 문제] 나무 자르기

import java.util.*;

public class Main {

    static int[] arr;
    static int m;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        int max = 0;

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int start = 0; // 무조건 나무를 가져갈 수 있는 부분
        int end = max; // 무조건 나무를 가져갈 수 없는 부분

        while (start + 1 < end) {
            int mid = (start + end) / 2;

            if (check(mid)) { // mid위치에서 나무를 가져갈 수 있는지 없는지 확인, 가져갈 수 있다면 mid는 start에 없다면 end에 넣음
                start = mid;
            } else {
                end = mid;
            }
        }

        System.out.println(start);
    }

    static boolean check(int cuttingHeight) { // cuttingHeight위치에서 나무를 가져갈 수 있는지 없는지 확인

        long sum = 0;
        long result;
        long tree;

        for (int i = 0; i < arr.length; i++) {
            tree = arr[i];
            if (tree >= cuttingHeight) {
                result = tree - cuttingHeight;
                sum += result;
            }
        }
        if (sum >= m) {
            return true;
        } else {
            return false;
        }
    }
}

이 문제는 나무들을 자를때 최소n만큼의 나무를 가져갈 수 있도록 하는 높이(최대값)을 구하는 문제이다. 

예를 들어서 높이가 20 15 10 17인 4개의 나무가 있고, 나무를 잘랐을 때 최소7높이의 나무를 가져가고 싶다면 높이의 최대값은 15가 된다. 

15높이에서 나무를 자르면 5,0,0,2만큼의 나머지가 생기므로 최소7의 조건을 만족하게 된다.

 

아이디어는, parametric search를 사용하였다. 즉 start(무조건 나무를 가져갈 수 있는 부분),end(무조건 나무를 가져갈 수 없는 부분)으로 나누고  start와 end의 중간값을 구해 중간값에서 나무를 가져갈 수 있는지 검사한는 것이다. 만약 중간값에서 나무를 가져갈 수 있다면 start에 중간값을 넣고 못 가져간다면 end에 중간값을 넣는다.

 

여기서 0의 높이에서는 나무를 무조건 가져갈 수 있기 때문에 start=0, 가장 큰 나무높이에서는 나무를 하나도 못가져 가기 때문에 end=나무의 최대높이로 초기화를 해주었다.

 

 총 4개의 나무(20 15 10 17)가 있고, 가져가고 싶은 나무의 길이는 최소7이라고 했을 때, 어떻게 최대높이는 구하는지 알아보자

초기 설정값은 start=0, end=20(나무의 최대높이), mid=10이다.

 

1. 처음에는 이런 모습이 된다. start무조건 되는 부분이기 때문에 O, start는 무조건 안되는 부분이기 때문에 X로 표시했다.

이후 mid값으로 check()함수를 실행하면 다음과 같이 된다.

 

2. mid가 10인 경우  10,5,0,7 총 22길이만큼 나무를 가져올 수 있다. start는 항상 나무를 가져올 수 있는 값이기 때문에 start에 mid값을 넣어준다. 여기서 중요한 것은 기존의 start값에서 새로운 start값 0~10범위에서는 모두 조건을 만족한다는 것이다. 

 

3. 다음번 실행하게 되면 위와같은 모습이 나오게 된다. mid=15인 경우 5,0,0,2 총 7길이만큼 가져올 수 있기 때문에 true가 된다. 그렇다면 다시 start에 mid값을 넣어주게 된다. 그리고 0~15범위의 값은 모두 조건을 만족한다는 의미이다.

 

4. 또 다시 실행하게 되고 mid=17인 경우 3,0,0,0 총 3길이만큼 가져올 수 있기 때문에 false가 된다. 즉 17위치에서는 나무를 가져올 수 없다는 의미이다. 그렇기 때문에 end에 mid값을 넣어준다.

 

5. 마지막으로 16에서도 나무를 가져올 수 없기 때문에 end에 mid값을 넣어준다. 그리고 while문조건이 start+1 < end 이기 때문에 while문을 빠져나오게 되고, 무조건 되는 경우 start를 출력하게 된다.

 

이 문제의 핵심은 start와 end 모두 각각 마지노선 값을 구한다는 점이다. start는 0->10->15순으로 값이 바뀌었는데, 이 세값은 모두 나무를 가져갈 수 있는 값들이다. 하지만 while문을 반복하면서 조건을 만족하는 최소한의 값, 마지노선 값을 찾아가고 있다. 0에서는 62를 가져올 수 있지만 15에서는 7을 가져올 수 있다. 위의 그림에서 초기의 start(0) ~ end(20)에서 서로 조금씩 자신의 조건을 만족하는 부분을 차지하고 더이상 조건을 따질 수 있는 값이 없다면 while문을 빠져나오게 된다.