백준 2805: 나무 자르기와 이분 탐색, 그리고 long

백준 2805번 나무 자르기는 가장 높은 절단 높이를 찾는 문제입니다. 그 높이로 나무를 잘랐을 때 필요한 길이 M 이상을 얻을 수 있어야 합니다.

높이를 하나씩 낮추는 방식은 느렸습니다

처음에는 가장 높은 나무부터 시작해 절단 높이를 1씩 낮췄습니다. 높이마다 모든 나무를 잘라 보고 잘린 길이의 합이 M 이상이면 멈췄습니다. 단순한 이중 반복문이었고 시간 초과가 났습니다.

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    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;
        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");

        int[] trees = new int[N];

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

        // 시작은 나무들 중에 가장 큰 값으로 시작한다.
        for (int i = Arrays.stream(trees).max().getAsInt(); i > 0; i--) {
            // 계속해서 나무를 잘랐을 때의 총 합을 초기화 한다.
            int sum = 0;
            // 나무의 개수만큼 반복한다.
            for (int tree : trees) {
                // 만약 나무가 자르려는 높이보다 크다면 잘라보고 그 높이를 합에 추가하고
                // 아니라면 그냥 넘어간다.
                if (tree > i) {
                    sum += (tree - i);
                } else continue;

                // 자르고 난 후의 나무의 높이가 원하는 길이를 얻었거나 더 얻었으면 루프 탈출
                if (sum >= M) {
                    bw.write(String.valueOf(i));
                    break;
                }
            }
            // 루프 탈출
            if (sum >= M) {
                break;
            }
        }
        bw.flush();
    }
}

높이의 범위를 절반씩 줄였습니다

절단 높이가 높아지면 얻는 나무의 양은 줄어듭니다. 이 성질을 이용해 높이를 이분 탐색했습니다.

중간 높이 mid에서 얻는 합이 M보다 작으면 더 낮게 잘라야 하므로 max = mid로 범위를 줄입니다. M 이상이면 더 높은 위치도 가능한지 확인하기 위해 min = mid + 1로 이동합니다. 반복이 끝난 지점 바로 아래인 min - 1이 조건을 만족하는 가장 높은 절단 높이입니다.

그런데 탐색 방법을 바꾼 뒤에도 합계를 int로 두었을 때는 오답이 나왔습니다. 문제의 큰 입력 범위를 다시 읽은 뒤 sum을 long으로 바꿔 해결했습니다. 나무 한 그루의 높이와 여러 나무에서 얻은 길이의 합은 따로 생각해야 했습니다.

Java

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    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;
        st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());



        int[] trees = new int[N];

        int max = 0;
        int min = 0;

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());

            if (trees[i] > max) {
                max = trees[i];
            }
        }

        while (min < max) {
            int mid = (max + min) / 2;
            long sum = 0;

            for (int height : trees) {
                if ((height - mid) > 0) {
                    sum += height - mid;
                }
            }

            if (sum < M) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        bw.write(String.valueOf(min - 1));
        bw.flush();
    }
}