백준 2512번 : 예산 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

예산 실버 2

 

📖 문제

 

이진 탐색이다. 하지만 국가 예산이라는 제한이 걸려있다.

때문에 무턱대고 이진탐색 범위를 0 ~ 10억 이렇게 설정하면 정말 쓴 맛을 느낄 수 있다. 

 

필자는 저렇게해서 삽질을 엄청하고, 반례는 다 통과하는데 75퍼에서 자꾸 틀리는 문제가 발생했다.

 

생각해보면 탐색을 할 범위를 명확하게 알고 설정해야하는데 무턱대고 큰 값을 설정한 것이 화근이였고

이진탐색을 할 줄만 알지 정확하게 이 알고리즘에 대해 이해하지 못함을 느꼈다.

 

따라서 이진탐색을 파볼 예정이다. 

 

요청 예산중 최댓값을 max로 이진 탐색한다. 

mid값을 각 요청 예산에 연산하여 mid > 요청 예산[i] 면 요청 예산값을 합 변수에 더하고,

크다면 mid값을 상한값으로 더한다.

그리고 국가예산과 합을 비교하여 

합 > 국가 예산  이면 mid 즉, 상한값이 너무 크다는 것으로 상한 값을 줄인다. back = mid - 1;

아니라면 더 큰 상한값을 찾기위해 상한값을 올린다. front = mid +1;

 

이런식으로 탐색하면 된다. 

 

핵심은 탐색 끝부분 back이 요청예산 max값이라는 것이다. 

 

 

---

🔅 문제 풀이

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] countries = new int[n];

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

        for (int i = 0; i < n; i++) {
            countries[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine()); // 총 예산

        // 예산 이진 탐색
        int front = 0, back = Arrays.stream(countries).max().getAsInt();
        int answer = 0;

        while (front <= back) {
            int mid = (back + front) / 2;
            long tmp = 0;

            for (int i = 0; i < n; i++) {
                if (countries[i] <= mid) {
                    tmp += countries[i];
                } else {
                    tmp += mid;
                }
            }
            // 배정된 예산값이 국가 예산 총액을 넘어가면 줄임
            if (tmp > m) {
                back = mid - 1;

                // 아니라면 올림
            } else {
                front = mid + 1;
                answer = mid;
            }
        }


        bw.write(answer + "");
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  탐색 범위를 명확히 알고, 어디를 탐색할건지 설정하자.