[백준]2512번. 예산(JAVA)

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

---

문제

---

풀이

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

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        long[] money = new long[n];
        long sum = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            money[i] = Integer.parseInt(st.nextToken());
            sum += money[i];
        }

        long total = Integer.parseInt(br.readLine());
        Arrays.sort(money);

        if(sum < total){
            System.out.println(money[n-1]);
        }else{
            long min = 0; // 예산 상한선의 최소값
            long max = money[n-1]; // 예산 상한선의 최댓값(최대 금액을 넘는 상한선을 둘 필요는 없음)
            long answer = 0;

            while(min <= max){
                long mid = (min + max) / 2;
                long s = 0;
                for(long m : money){
                    if(m >= mid){
                        s += mid;
                    }else{
                        s += m;
                    }
                }

                if(s > total){
                    max = mid - 1;
                }else{
                    min = mid + 1;
                    answer = mid;
                }
            }
            System.out.println(answer);

        }

    }

}

 

이분탐색을 이용한 문제풀이이다. 

상한선에 대한 정확한 인지를 한 후에 문제를 풀어야 한다.

1. 모든 예산의 합이 총예산보다 적다면 가장 비싼 예산을 상한으로 잡는다.(최고 예산보다 상한이 높을 이유는 없다.)

2. 1번의 경우가 아니라면 상한선의 최솟값은 0원에서 최대 최고 예산까지 가능하다.

2-1 0~최고예산 사이의 이분탐색을 진행하여 값을 출력한다.

 

이분탐색에서 중요한 것은 min <= max를 조건으로 쓰는 상황에 대한 인지가 되어야 한다.

단순하게 생각하면 이해가 안 될 수도 있지만 값으로 한번 살펴보자.

1 2 3 세 개의 값이 있고, 내가 찾는 값은 3이라고 하자.

1이 min, 3이 max가 될 것이고 2가 mid가 된다.

그럼 목푯값보다 mid가 작으므로 min이 3이 될 것이다. 여기서 min < max 조건이라면 mid=2 인 상태로 끝나게 된다. 

따라서 등호가 들어가야 한다.