BOJ 2512 - 예산

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

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();
    }

}