[알고리즘] 백준 2805 나무자르기 - JAVA

www.acmicpc.net/problem/2805

2805번: 나무 자르기

이분 탐색 문제이다.

 

right값을 통나무중에서 가장 긴 통나무로 초기화 해준 후 m에 가장 근접하는 값을 찾아주면 된다.

 

맞왜틀..이 계속 나왔는데 뭔지 보니까 통나무의 길이가 최대 10억까지 들어갈 수 있으므로 구하는 과정에서 int값을 넘어가기 때문이였다.

 

단위!!! 한번씩 꼭 확인하는 습관을 들여야겠다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int m;
    static int h;
    static int[] tree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        tree = new int[n];

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

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

        Arrays.sort(tree);
        System.out.println(binarySearch());
    }

    static int binarySearch() {
        int left = 0;
        int right = tree[n - 1];

        while (left <= right) {
            int mid = (left + right) / 2;
            long current = 0;

            for (int i = 0; i < n; i++) {
                int temp = 0;

                if (tree[i] - mid >= 0) {
                    temp = tree[i] - mid;
                }

                current += temp;
            }

            if (current < m)
                right = mid - 1;
            else if (current > m)
                left = mid + 1;
            else
                return mid;

        }
        return right;
    }
}