[Java] 백준 1114번 - 통나무 자르기

통나무 최대 c번 자를 수 있고, 자르는 위치는 정해져 있다. 통나무를 잘라서 만들 수 있는 길이의 최대값의 최소값을 구하는 문제이다. 

최대값의 최소값이라는 문구가 주어지면 이분 탐색의 방법을 사용하는 것이 가능하다. 이분 탐색은 주어진 조건을 만족하는 최소값이나 최대값을 log(n)의 시간 복잡도에 찾을 수 있기 때문이다.

잘리는 위치는 정해져있으므로 누적합을 이용해서 통나무의 길이를 더하고, 만약 누적합이 허용되는 길이보다 길다면, 이전의 위치에서 통나무를 잘라준다. 자르지 못하는 상황에서 길이를 초과한 경우에는 break를 이용해 통나무 탐색을 빠져나와서 left와 right의 값을 변경해준다.

첫번째 통나무의 길이를 최소로 하라는 조건이 주어져 있기 때문에, 뒤에서부터 통나무를 자른다. 만약 통나무를 자르고, 1번의 기회가 남았다면, 첫번째로 자를 수 있는 곳이 정답이 된다.

 

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();

        String[] spt = line.split(" ");
        Long l = Long.parseLong(spt[0]);
        int k = Integer.parseInt(spt[1]);
        int c = Integer.parseInt(spt[2]);

        line = sc.nextLine();
        spt = line.split(" ");
        List<Long> pos = new ArrayList<>();
        pos.add(0L);
        pos.add(l);
        for (int i = 0; i < k; i++) {
            pos.add(Long.parseLong(spt[i]));
        }
        pos.sort((a, b) -> (int) (a - b));
        long left = 0;
        long right = l;
        long ansFirst = 0;
        long ansLongest = l;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long cutCnt = 0;
            long firstCut = -1;
            long diff = 0;
            for (int i = k; i >= 0; i--) {
                diff += pos.get(i + 1) - pos.get(i);
                if (diff > mid) {
                    diff = pos.get(i + 1) - pos.get(i);
                    cutCnt++;
                    if (diff > mid) {
                        cutCnt = c + 1;
                        break;
                    }
                }
            }
            // 첫번째를 자를 수 있는지 확인한다.
            // 한번이라도 자를 수 있으면 첫번째가 최소 길이가 된다.
            if (cutCnt < c) {
                firstCut = pos.get(1);
            } else {
                firstCut = diff;
            }
            if (cutCnt <= c) {
                ansLongest = Math.min(mid, ansLongest);
                ansFirst = firstCut;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(ansLongest + " " + ansFirst);
        sc.close();

    }
}