백준 2805번
https://www.acmicpc.net/problem/2805

문제

---

생각하기

---

예전에 풀었던 랜선자르기 문제랑 굉장히 비슷하다.
알고리즘또한 이진탐색을 사용한다는 점 또한 같다

처음에 이진탐색을 사용하지 않고 높은 곳에서 깎아서 내려가는 방식으로 했는데
범위가 워낙 넓은 터라 바로 시간초과가 발생했다.

코드를 살펴보면,
이진탐색binary_search가 핵심이다.

min은 나무의 가장 아래인 0의 값으로 처음 설정해주고 max는 나무의 가장 높은 값으로 설정한다.
Collections.max(treeList)를 통해서 treeList에서 가장 높은 나무를 찾아왔다.

이진탐색을 실행하기위해서 binary_search 함수를 따로 만들었다.

우리가 찾는 절단 위치를 mid변수를 통해서 찾게된다.
mid 값을 절단 위치로 설정하고 treeList의 값들을 순차적으로 mid값 보다 같거나 큰 나무들만 선택하여 절단해서 해당 절단된 나무의 길이 합 sum의 값이 일치 할때 까지 반복하는 것이다.

TMI

이 문제를 처음 풀때 범위가 이진탐색을 써야되겠다는 생각을 못했다.
문제를 보고 나서 어떤 알고리즘을 사용해야 되는지 안목을 키울 필요가 있어보인다.

전에 풀었던 랜선 자르기 문제랑 굉장히 비슷하다고 느꼈음에도 불구하고
이진탐색을 떠올리지 못한 나..

정신 좀 차리라고 제발!!!!

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, maxHeight;
    private static long ans;
    private static int[] treeHeights;

    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();

        ans = binarySearch(0, maxHeight);
        sb.append(ans);
        return sb.toString();
    } // End of solve()

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

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

        if (treeSum < M) {
            return binarySearch(low, mid - 1);
        } else {
            return binarySearch(mid + 1, high);
        }
    } // End of binarySearch()

    private static long check(long mid) {
        long sum = 0;
        for (int i = 0; i < N; i++) {
            if (treeHeights[i] > mid) {
                sum += (treeHeights[i] - mid);
            }
        }
        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());

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