백준 알고리즘 2512번: 예산

문제 정보

---

 

2512번: 예산

 

핵심

---

 

백준 알고리즘 1654번: 랜선 자르기

위 문제와 동일한 방식으로 풀이할 수 있는 이분탐색 문제 중 하나!

 

각 예산 요청에 대하여 가능한 최대 총 예산을 가지도록 하는 예산의 상한액을 구하는 문제이다

• N : 지방의 수 ( N >= 3, N <= 10,000 )
• ( 1 <= 각 예산 <= 100,000 )
• M : 총 예산 ( M >= N, M <= 1,000,000,000 )

 

0부터 가장 많은 예산 요청 금액의 범위에서 시작하여, 이분 탐색을 진행하며 적절한 예산의 상한액을 구하면 된다

다만, 이전 문제인 랜선 자르기에서와 동일하게 max 값은 최대값 + 1을 초기값으로 지정해야 한다

 

// CASE-3
5
70 80 30 40 100
450

이 경우 max 가 100으로 이분탐색을 시작할 텐데, min < max 조건이 존재하기 때문에 min=max 인 시점 즉, min = 100 인 시점에 아마 종료가 될 것이다?

 

하지만 풀이 내에서의 max는 max 값 자체를 포함하고 있지 않은 미만의 개념이므로 위 경우에서도 결국 마지막에 min - 1 = 99 가 나오게 되는 것이다

max + 1 을 통하여 max가 답에 포함될 수 있도록 해주어야 한다!

 

풀이

---

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] requests = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(br.readLine());

        int min = 0;
        int max = 0;
        for(int i=0; i<N; i++) {
            requests[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, requests[i]);
        }

        max++;
        while(min < max) {
            int mid = (min + max) / 2;

            int sum = 0;
            for(int i=0; i<N; i++) {
                sum += Math.min(mid, requests[i]);
            }

            if(M < sum) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        System.out.println(min - 1);
    }
}

 

 

Source Code on GitHub

---