카테고리: 이분탐색

문제

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

풀이 방식

나무 길이의 최댓값부터 1씩 줄여나가며 최적해를 찾는 것은 시간 초과가 걸립니다. 따라서 Parametric Search를 이용하여 문제를 풀어보겠습니다.

1. 자른 나무들의 합이 필요한 나무의 길이보다 크거나 같은지 체크

 static boolean isTrue(int[] arr, int height, int m){
        long sum = 0; // int 말고 long이어야함
        for(int tree : arr){
            if(tree > height){
                sum += tree - height;
            }
        }

        return sum >= m;
 }

2. 조사범위를 줄여가며 이분 검색

최종 코드

Set을 이용한 풀이입니다.

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


class Main {

    static boolean isTrue(int[] arr, int height, int m){
        long sum = 0;
        for(int tree : arr){
            if(tree > height){
                sum += tree - height;
            }
        }

        return sum >= m;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] trees = new int[n];
        st = new StringTokenizer(br.readLine());
        int max = 0;
        for(int i=0; i<n; i++){
            int height = Integer.parseInt(st.nextToken());
            trees[i] = height;
            max = Math.max(max, height);
        }

        //절단기의 높이는 0 ~ max 까지의 범위 안에서만 움직일 수 있다.
        int start = 0;
        int end = max;
        int optimal_height = 0;

        while(start <= end){
            int mid = (start + end) / 2;
            if(isTrue(trees, mid, m)){
                start = mid + 1;
                optimal_height = mid;
            }else{
                end = mid -1;
            }
        }

        System.out.println(optimal_height);

    }
}