백준, 예산(2512, java)

문제 설명

여러 지방에 예산을 분배해야 한다. 하지만, 국가 예산의 총액은 이미 정해져 있어 총액 내에서만 분배가 가능하다. 만일 지방에서 요구한 예산이 기준보다 작다면 요구한 예산을 분배하고 크다면 기준을 분배한다. 이때 기준의 최댓값을 구하는 문제이다.

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

2512번: 예산

참고!

예산 기준이 정해지면 (예산 기준 * 지방의 수)가 총 예산 안에 들어갈 필요는 없다. 어차피 예산 기준보다 작은 예산들은 각 지방이 요청한 만큼만 주기 대문이다. 예산 기준보다 큰 예산만 예산 기준에 맞춰준다는 의미다.

문제 풀이

첫 번째 접근

지금까지 풀어왔던 이진 탐색 문제와 유형이 비슷하다.

 

이진 탐색은 범위를 정하는 것이 중요한데, 범위는 0부터 각 지방의 예상 요청 중 최댓값 +1로 정해줬다. +1을 해주는 것은 우리가 upper bound로 문제를 풀 것이기 때문이다. uppder bound는 mid+1로 start를 지정해준다. 이때 mid+1 한 값이 end와 같아져서 반복문을 탈출하면 start-1로 인하여 답이 -1 작게 나온다. 그러므로 end+1을 해줘서 언제나 답 보다 +1 위에 있도록 하는 것이다.

 

그리고 비교할 기준이 필요한데, 나는 이를 check 함수를 따로 만들어 줘서 구해줬다. 만일 기준인 mid보다 지방 예산이 작다면 그 예산을 그냥 더해주고 더 크다면 mid를 더해줬다. 이렇게 구한 합을 가지고 전체 예산하고 비교했다.

 

만일 전체 예산이 더 크거나 같다면 이는 기준을 높여줘도 된다는 의미이다. 왜냐하면 우리는 기준의 최댓값을 구하는 것이기 때문이다. 때문에 start를 mid+1로 넣어서 기준을 높인다. 그게 아니고 전체 예산이 더 작다면 이는 기준을 낮춰야 한다는 의미로 end를 mid로 넣어준다.

 

코드

java

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

import java.util.*;

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[] budgets = new int[N];
        String[] input = br.readLine().split(" ");

        for(int i=0; i<N; i++){
            budgets[i] = Integer.parseInt(input[i]);
        }

        int allBudget = Integer.parseInt(br.readLine());

        Arrays.sort(budgets);

        long start = 0;
        long mid = 0;
        long end = budgets[N-1]+1;
        while(start < end){
            mid = (start+end)/2;

            long tmp = check(budgets, mid);
            System.out.println(start + " " + mid + " " + end);
            System.out.println(tmp);
            if(tmp > allBudget){
                System.out.println("기준을 낮춰야 한다.");
                //기준을 낮춰야 한다.
                end = mid;
            }else{
                System.out.println("기준을 높여야 한다.");
                //기준을 높여야 한다.
                start = mid+1;
            }

        }

        System.out.println(start-1);

    }

    public static long check(int[] budgets, long standard){

        long sum = 0;
        for(long budget : budgets){
            if(budget <= standard){
                sum += budget;
            }else{
                sum += standard;
            }
        }

        return sum;
    }


}