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

📒 문제

📒 입출력

🌻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long tree[] = new long[N];
        long max = 0;
        for (int i = 0; i < N; i++) {
            tree[i] = sc.nextInt();
            if (tree[i] > max) max = tree[i];
        }
        long left = 0, right = max, mid, height = 0;
        boolean flag = false;
        while (left <= right) {
            long sum = 0;
            mid = (left + right) / 2;
            for (int i = 0; i < tree.length; i++) {
                if (tree[i] > mid) sum += tree[i] - mid;
                else continue;
            }
            if (sum == K) {
                System.out.println(mid);
                flag = true;
                break;
            } else if (sum < K) right = mid - 1;
            else {
                left = mid + 1;
                height = mid;
            }
        }
        if (!flag) System.out.println(height);
    }
}

💡 정리하기

👉 이분탐색인데 애초에 감을 못잡았었다. 그래서 같이 공부하는 선배 도움을 받아서 조금씩 풀어갈 수 있었다. 입력에서 나무의 높이 합은 항상 M보다 크거나 같기 때문에, 라는 부분을 잘 봤어야 했다. while문에서도 left != right라고 했었는데 left <= right 가 맞았다.