<백준> 2805번 자바 알고리즘 [이분 탐색]

import java.util.*;

public class Main
{
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        
        int[] arr = new int[n];
        
        int max = 0;
        // arr 셋팅 
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
            if(arr[i] > max){
                max = arr[i];
            }
        }
        
        int min = 0;
        
        while(min < max){
            int mid = (min + max) / 2;
            long sum = 0;
            for( int a : arr){
                if(a > mid){
                    sum += a - mid;
                }
            }
            
            if(m > sum){
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        
        System.out.println(min - 1);
	}
}

 

upperbound 방식을 이용하여 풀었다

 

upperbound란 

 

예를 들어 

{1, 3, 3, 4, 5, 5, 6, 7, 8, 8, 10}에서 3을 초과한 최초의 값을 구한다고 하자

 

여기서 3은 중복되어 있으므로 3의 index에서 가장 오른쪽 값을 구하고 거기에 + 1을 하는 원리이다

 

min = 0

max = 10

mid = 10 / 2 = 5

 

arr[5] = 5 와 3 을 비교한다

arr[5]가 더 크므로 

max를 줄여야 한다.

 

max = mid = 5

mid = 5 / 2 = 3

 

arr[3] = 4 와 3을 비교한다

arr[3]이 더 크므로

다시 max를 줄인다

 

max = mid = 3

mid = 3 / 2 = 2

 

arr[2] = 3 와 3을 비교한다

둘이 같다.

min  = mid  + 1 을 한다

 

그러면 min 과 max 가 같으므로 값은 arr[3] 즉 4 이다.