BOJ 2512 - 예산

[jusung-c]

---

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

• 지방의 수 N (3 <= N <= 1만)
• 각 지방의 예산들은 모두 1 이상 10만 이하
• 나라의 총 예산 M (N <= M <= 10억)

---

아이디어

정해진 총액 이하에서 가능한 한 최대의 총 예산을 구해야 하는 문제로 " 최대 " 라는 키워드가 나왔으니 먼저 이분 탐색을 고려해본다.

원래 문제

• 나라의 총 예산 M을 최대한 사용할 수 있는 예산 상한선은 얼마인가?

이분탐색을 위해 상한선을 H라고 하고 문제를 뒤집어서 Yes or No 문제로 만든다.

뒤집어서 만든 Yes or No 문제

• 상한선이 H일 경우 나라의 총 예산 M 안에서 배정이 가능한가?

이분탐색을 진행해서 상한선 H 마다 Yes or No를 채우고 마지막 Yes인 H를 찾아낸다.
H의 범위는 1~요청 예산의 최대값.

---

시간 복잡도

• Yes or No 질문을 한번 할 때마다 걸리는 시간은 O(N)
• 이분 탐색 진행시 탐색 범위가 1~10만 이므로 최대 질문 수는 log 10만이 돼서 O(log 10만)의 시간 복잡도를 가진다.
• 총 O(N log 10만)의 시간 복잡도를 가져서 1초안에 풀이가 가능하다.

---

점점 풀이에 익숙해지는 것 같다 오예

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] plz;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        plz = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= N; i++) {
            plz[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
    }

    static void pro() throws IOException {
        // 이분탐색
        int L = 0;
        int R = 0;
        for (int i = 1; i <= N; i++) {
            R = Math.max(plz[i], R);
        }

        int ans = 0;

        while (L <= R) {
            int mid = (L + R) / 2;

            if (YesOrNo(mid) == true) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }

        bw.write(ans+" ");
    }

    static boolean YesOrNo(int H) {
        int sum = 0;

        for (int i = 1; i <= N; i++) {
            sum += Math.min(H, plz[i]);
        }

        if (sum <= M) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}

[ghdcksgml1]

코드가 아주 깔끔하네여~~