BOJ 2805 - 나무 자르기

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

2805번: 나무 자르기

 

'최댓값'이라는 키워드 나왔으므로 이분 탐색 고려해보기. 

 

원래 문제

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

 

매개변수 설정 후 뒤집은 문제

• 정답인 절단기 높이를 매개변수 H로 설정
• 어떤 절단기 높이(H)로 잘랐을 때, 원하는 길이 M만큼을 얻을 수 있는가?
• Yes/No 문제로 변신

 

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

// 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;
    }
}

 

 

 

이분탐색으로 H를 찾아내기 위해 먼저 나무 리스트를 정렬해주어야 한다.

정렬 후 Yes/No를 채워서 가장 마지막 Yes를 찾아낸다.

 

 

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+" ");
}

 

시간복잡도

한 번 질문 시에 O(N)만큼 걸리고 H의 범위가 20억이므로 질문 횟수는 최대 log 20억 번 이므로

O(N log20억), 즉 O(N x 31)의 시간 복잡도를 가진다. 

 

 

변수 타입 설정

나무 개수 : N (1 ~ 100만)

필요한 나무 길이 : M (1 ~ 20억) -> Long

절단기 높이(정답) : H (1 ~ 20억) -> Long

 

 

구현

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

}