백준 2805번 나무 자르기 Java

https://www.acmicpc.net/problem/2805

문제

---

생각하기

---

• 이분 탐색 문제이다.

동작

if (ret >= M) {

이게 핵심인 이유가 문제에서 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

M보다 크거나 같은 조건이 정답이 된다.

번외로 지금 구현한 방식의 이분 탐색 재귀보다 아래의 방식을 AI는 추천했으니 참고해봐야한다.

private static String solve() {
    // ... 이전 코드 생략 ...
    long max = 0; // 최댓값 찾기
    for(int h : arr) if(h > max) max = h;

    // 초기 정답을 -1 (또는 0)로 설정하고 재귀 시작
    long result = binarySearch(0, max, -1);
    return String.valueOf(result);
}

// 현재까지의 정답(currentAns)을 인자로 넘기는 방식
private static long binarySearch(long low, long high, long currentAns) {
    // 1. 재귀 종료 조건 (Base Case)
    if (low > high) {
        return currentAns; // 탐색이 끝나면 지금까지 찾은 최적의 답을 반환
    }

    long mid = (low + high) / 2;
    long totalCut = check(mid);

    // 2. 재귀 호출 (Recursive Step)
    if (totalCut >= M) {
        // mid는 정답 후보. 더 좋은 답을 찾으러 오른쪽으로 이동
        // 이때, 현재까지 찾은 정답이 mid라고 기록하며 재귀 호출
        return binarySearch(mid + 1, high, mid);
    } else {
        // mid는 정답이 아님. 반드시 왼쪽으로 이동
        // 정답 후보는 변하지 않았으므로 currentAns를 그대로 전달
        return binarySearch(low, mid - 1, currentAns);
    }
}

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int max = Arrays.stream(arr).max().orElse(Integer.MIN_VALUE);
        long ret = binarySearch(0, max);

        sb.append(ret);
        return sb.toString();
    } // End of solve()

    private static long binarySearch(long low, long high) {
        if (low > high) return -1;

        long half = (low + high) / 2;
        long ret = check(half);

        if (ret >= M) {
            long temp = binarySearch((int) (half + 1), high);
            if (temp == -1) {
                return half;
            } else {
                return temp;
            }
        } else {
            return binarySearch(low, half - 1);
        }
    } // End of binarySearch()

    private static long check(long height) {
        long sum = 0;

        for (int i = 0; i < N; i++) {
            if (arr[i] > height) {
                sum += arr[i] - height;
            }
            if (sum > M) break;
        }

        return sum;
    } // End of check()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class