BOJ 2805 - 나무 자르기

[jusung-c]

---

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

---

아이디어

'최댓값'이라는 키워드가 나와서 이분탐색을 먼저 생각했다.

원래 주어진 문제

• "원하는 길이 M 만큼 얻을 수 있는 최대 절단기 높이는 얼마인가?"

이분 탐색을 위해 최대 절단기 높이를 H 매개변수로 설정 후 문제를 뒤집어서 Yes or No 문제로 바꿔준다.

뒤집어서 만든 Yes or No 문제

• "어떤 높이 H로 잘랐을 때 원하는 길이 M만큼을 얻을 수 있는가?"

나무 리스트를 정렬해준 후 이분 탐색으로 H마다 Yes or No를 물어봐서 마지막 Yes인 H의 높이를 찾아낸다.

---

시간 복잡도

위의 Yes or No 문제를 한번 물어보는 데 걸리는 시간은 나무들을 H높이로 잘라내서 더해주기만 하면 되기 때문에 O(N)이다.

이분 탐색은 H의 범위가 20억 이므로 최대 질문 횟수가 log 20억이라서 O(log 20억)의 시간 복잡도를 가진다.

따라서 총 O(N log 20억)의 시간 복잡도를 가져서 1초안에 풀이가 가능하다.

---

류호석님 자료 보고 따라서 풀어봤는데 이해하는데 오래 걸렸지만 좋은 방법인거 같네용 😲

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static long M;
    static int[] trees;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        // 나무 개수
        N = Integer.parseInt(st.nextToken());

        // 필요한 나무의 길이
        M = Long.parseLong(st.nextToken());

        // 나무 리스트
        trees = new int[N + 1];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() throws IOException {
        // 나무 리스트 정렬
        // Arrays.sort(trees, 1, N);

        // H의 범위인 L과 R 설정 H (1 ~ 20억)
        long L = 0;
        long R = 2000000000;

        long ans = 0;

        // 이분탐색 진행
        while (L <= R) {
            long mid = (L + R) / 2;

            // mid가 Yes면
            if (YesOrNo(mid) == true) {
                // ans 갱신
                ans = mid;

                // 범위 좁히기
                L = mid + 1;
            } else {
                // 범위 좁히기
                R = mid - 1;
            }
        }

        bw.write(ans+" ");
    }

    // Yes or No 채우기
    static boolean YesOrNo(long H) {
        // H 높이로 잘라서 M만큼 얻을 수 있는가? Yes or No?
        long sum = 0;

        // 자른 나무 길이 계산
        for (int i = 1; i <= N; i++) {
            if (trees[i] > H) {
                sum += trees[i] - H;
            }
        }

        if (sum >= M) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}

[ghdcksgml1]

매개변수 탐색,, 처음에 이해하기 쉽지않지

[jusung-c]

쉽지 않네유 😥

[jusung-c]

이분탐색을 나무리스트에 하는 게 아니니까 나무 리스트 정렬 안해도 되네요
정렬하는 코드 빼니까 시간 반으로 줄었다..