[백준] 2512 예산 java 풀이

1. 문제 설명 📌

문제 설명

2. 접근 방식 🗃️

KEY WORD : Binary Search, Parametric Search

• (1) 모든 지방 예산의 합 <= 총 예산, 그대로 예산 책정 하고, 제일 컸던 지방 예산을 출력
• (2) 모든 지방 예산의 합 > 총 예산: 예산 최소값과 최대값 사이에서 이분 탐색을 통해, 모든 예산을 처리하면서 최대인 값을 찾아서 출력

(1) Parametric Search 쓰인 곳

모든 예산을 처리할 수 있는 최대값 구하기 ➜f(d) = 예산 상한액이 d일 때, 이걸로 총 예산 M 내에서 전부 처리 가능한가? 여러 개

위와 같이 최적화 문제를 결정 문제 여러개로 바꾸어 푼다.

f(d) = true가 나오는 값 중 최대한 오른쪽에 있는 값을 구하면 답이다. (즉 f(d) = true가 되는 d의 최대값을 구한다.)

3. 코드 소개 🔎

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


public class Main {
    static int N;
    static int M;
    static int [] budget;

    public static void main(String[] args) throws IOException {
        int sum = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        budget = new int [N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            budget[i] = Integer.parseInt(st.nextToken());
            sum += budget[i];
        }
        Arrays.sort(budget);
        M = Integer.parseInt(br.readLine());
        if(sum < M) {
            System.out.println(budget[budget.length-1]);
            return;
        }
        System.out.println(binary_search());
    }

    public static int binary_search() {
        int start = 1;
        int end = budget[budget.length-1];

        while (start <= end){
            int mid = start + (end - start)/2;
            if(f(mid)) start = mid + 1;
            else end = mid -1;
        }
        return start - 1;
    }

    public static boolean f(int mid){
        int sum = 0;
        for (int j : budget) {
            sum += Math.min(j, mid);
        }
        return sum <= M;
    }
}

4. 배운 것들 🎯

(1) 내가 T/C를 찾아볼 수 밖에 없게 만든 것들

a. true, false 구간 산정

처음에 f(d)함수의 return 값을 sum < M 으로 했다. mid가 상한액일 때 총합이 총 예산과 같아도 true가 나와야 하는데, 그것을 산정하지 않았다.

해당 반례

3
1 3 5
8

b. 이분탐색 최대값, 최소값 구간 산정

처음에는 int start = budget[0]로 두어, 지방 예산 중 최소값으로 정했다. 이러면 상한액이 지방 예산의 최소값 보다도 작아져야 하는 경우를 계산하지 못한다.

해당 반례

5
100 100 100 100 100
10