[JAVA] 백준 2805번_나무 자르기

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

2805번: 나무 자르기

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] tree;
    static int N, M, mid;
    static long tmpSum, ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        tree = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //이분 탐색을 위해 나무 길이 오름차순 정렬
        Arrays.sort(tree);
        int left = 0;
        int right = tree[N - 1];
        while (left <= right) {
            mid = (left + right) / 2;
            tmpSum = getWood(mid);
            if(tmpSum < M) //잘려나온 나무 길이가 M 미만일 경우 -> mid가 더 작아야 함
                right = mid - 1;
            else { //잘려나온 나무 길이가 M 이상일 경우 -> 답을 갱신하고, mid가 더 클 수 있는지 갱신
                ans = mid;
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }
	//기준이 mid일 경우, 잘라서 나오는 나무 길이의 총합
    private static long getWood(int mid) {
        long sum = 0;
        for (int t : tree) {
            if(t >= mid)
                sum += (t - mid);
        }
        return sum;
    }
}

💡 이분 탐색

- 누적 합 구하는 과정에서 시간 초과가 발생할까봐 dp를 이용했는데 그냥 구해도 될듯...

 

풀이

• 시작 지점과 끝 지점을 0, 나무 중 길이 최소로 설정 후 이분 탐색을 통해 특정 기준 마다 나오는 나무의 총합이 M 이상이도록 하는 기준 탐색
• 잘려나온 나무 길이를 계산할 때, 그 값이 long형일 수 있음에 유의할 것
• tmpSum < M인 경우, tmpSum값을 키우기 위해선 mid를 줄여야 함 (반대)