<Algorithm> 87. 2512번 예산

1. 2512번 예산

• 이문제를 풀면서 이분탐색에 대한 나의 생각의 문제점을 발견 할 수 있었다.

• 이분탐색은 반을 나누어 대소비교를 통해 1/2 1/4 씩 줄어드는 것인데 1/2 나눠진 것이 또 돌아간다고 생각했다.

• 풀이를 해보면 간단하지만 접근하는 방법이 그리 간단하지는 않은 문제라고 생각한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] bgt = new int[n];
        int end = -1;
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            bgt[i] = Integer.parseInt(st.nextToken());
            end = Math.max(end,bgt[i]);
        }
        
        int lim = Integer.parseInt(br.readLine());
        
        while(start<=end) {
            
            int total = 0;
            int mid = (start+end)/2;
            
            for(int i = 0; i < n; i++) {
                total += Math.min(bgt[i], mid);
            }
            
            if(total <= lim)  {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        System.out.println(start-1);
    }
}

참고 & 출처