[백준] 2512번: 예산

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

예제 입력 1

4
120 110 140 150
485

예제 출력 1

127

예제 입력 2

5
70 80 30 40 100
450

예제 출력 2

100

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N=Integer.parseInt(br.readLine());
        StringTokenizer st=new StringTokenizer(br.readLine());

        int[] request=new int[N];
        long tmp=0;
        int max=0;
        for(int i=0;i<N;i++){
            request[i]=Integer.parseInt(st.nextToken());
            tmp+=request[i];
            max=Math.max(max,request[i]);
        }

        long M=Long.parseLong(br.readLine());

        // 모든 요청을 배정할 수 있는지
        if(tmp<=M){
            System.out.println(max);
            System.exit(0);
        }

        // 모든 요청을 배정할 수 없다면 적당한 예산 구하기
        int left=0;
        int right=max;
        int mid=(left+right)/2;

        while(left<=right){
            tmp=0;
            mid=(left+right)/2;

            for(int i=0;i<N;i++){
                if(request[i]<mid) tmp+=request[i];
                else tmp+=mid;
            }

            if(tmp<=M){
                // 예산안에 맞춰서 설정한 경우
                // 예산의 최대값 구하도록
                left=mid+1;
            }else{
                right=mid-1;
            }
        }

        System.out.println(right);
    }
}

모든 지방에 예산을 배정할 수 있도록 상한액의 최대값을 구하는 문제이다.

상한액을 정한 뒤 예산을 초과한다면 상한액을 줄이고

예산을 초과하지 않는다면 상한액의 최대값을 구해야하기 때문에 상한액을 크게 만든다.

모든 요청을 배정할 수 있을 때

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

if(tmp<=M){
    System.out.println(max);
    System.exit(0);
}

임시 상한액을 정했을 때 모든 요청을 배정했을 때의 금액을 모두 더하는 tmp 변수와

요청이 들어온 금액 중 가장 큰 값 max 변수를 지정한다.

이때, tmp 변수값이 예산을 초과하지 않는다면 모든 요청을 그대로 배정하면 되기 때문에 max 값을 출력하고 프로그램을 종료한다.

이분탐색

int left=0;
int right=max;
int mid=(left+right)/2;

while(left<=right){
    tmp=0;
    mid=(left+right)/2;

    for(int i=0;i<N;i++){
        if(request[i]<mid) tmp+=request[i];
        else tmp+=mid;
    }

    if(tmp<=M){
        // 예산안에 맞춰서 설정한 경우
        // 예산의 최대값 구하도록
        left=mid+1;
    }else{
        right=mid-1;
    }
}

System.out.println(right);

모든 요청을 그대로 배정하지 못한다면 상한액을 구해야한다.

이분탐색을 통해 0 ~ max 값 중 상한액을 탐색한다.

mid를 상한액으로 지정하고 tmp값을 구했을 때 예산보다 작거나 같으면 그대로 상한액을 출력하는 것이 아니라 상한액의 최대값을 구해야하기 때문에

left 변수를 mid+1의 값으로 지정해준다.

반대로 예산을 초과하게 된다면 상한액을 낮춰야하기 때문에 right 변수를 mid-1의 값으로 지정해준다.

이 과정을 left 변수가 right 변수보다 커질때까지 반복한다.

left=mid+1 을 해주고 right=mid-1을 해주기 때문에 언젠가는 꼭 left가 right보다 커질 수 밖에 없다.

while문을 벗어나게 되면 right가 left보다 작아지게되는데 예산을 넘기면 안되기 때문에 값이 더 작은 right 변수를 출력해주면 답이 된다.

원래 이분탐색을 진행하기 위해서는 탐색해야할 범위를 정렬해주고 시작해야하는데

이 문제에서 상한액은 주어진 배열이 아니라 숫자이기 때문에 따로 정렬할 필요없이 탐색을 진행하면 된다.