2022.06.25 백준 Q2805

학습내용 : 이분탐색, Upper Bound,Lower Bound

이 문제는 빠른 시간 내에 최소 나무 길이에 부합하는 잘라야 하는 나무의 높이를 설정하는 문제이다. 처음에 필자는 treeArray를 크기 순으로 나열하고 두번째로 큰 부분부터 잘린 나무의 합을 구하고 그 값이 원하는 나무 길이보다 작으면 treeArray[]의 index를 하나씩 줄이고 만약 처음으로 원하는 나무 길이가 작으면 treeArray[index]+(m-sum)/index값보다 큰 나무의 수로 값을 구했다. 그랬더니 시간 복잡도가 O(n!)이라 시간 초과가 나와 이분 탐색으로 시간 복잡도를 줄였다.

 

 

long min=0,max = 0;
for(int i : treeArray){
    max =Math.max(i,max);
}

윗 코드에서 array에서 min과 max를 구할 때 초기값을 둘다 0으로 한 이유는 만약 4 16/n 4 4 4 4인 경우가 있을 때 4이하로 내려갈 수 없어 값을 구할 수 없다. 따라서 min은 항상 0이고 max만 구해준다

 

 

while(true){
    sum=0;
    if(max==min){
        System.out.println(max-1);
        break;
    }
    long medium = (max+min)/2;
    for(long i:treeArray){
        if(i>medium){
            sum+=i-medium;
        }
    }
    if(sum>=m){
        min=medium+1;
    }else{
        max=medium;
    }
}

의문점 1: lower Bound가 아닌 upper Bound로 구해야 하는 이유

의문점 2: sum==m일 때도 min=medium+1으로 처리해야하는 이유

의문점 3: sum<m일 때 max=medium-1이 아닌 max=medium으로 처리해야하는 이유

---추후 추가 예정----

 

 

 

-코드-

package BaekJoon2805;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int [] treeArray;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String bfS = bf.readLine();
        StringTokenizer st = new StringTokenizer(bfS);
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        treeArray = new int[n];

        bfS = bf.readLine();
        st = new StringTokenizer(bfS);
        for(int i=0;i<n;i++) treeArray[i] = Integer.parseInt(st.nextToken());
        long min=0,max = 0;
        for(int i : treeArray){
            max =Math.max(i,max);
        }
        long sum;
        while(true){
            sum=0;
            if(max==min){
                System.out.println(max-1);
                break;
            }
            long medium = (max+min)/2;
            for(long i:treeArray){
                if(i>medium){
                    sum+=i-medium;
                }
            }
            if(sum>=m){
                min=medium+1;
            }else{
                max=medium;
            }
        }
    }
}