[BOJ] 2512번 - 예산 (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

이 문제를 처음 봤을 때 당연히 이분탐색으로 풀어야 겠다고 생각했다.

구해야할 상한액을 [0 ~ 요청할 금액 중 가장 큰 값] 구간에서 이분탐색을 한다.

 

아래의 코드는 이를 구현한 것이다.

이때 solve(mid) 는 배정된 예산의 합을 반환한다.

이를 기준으로 start와 end를 변경해가며 최대 상한액을 찾는다.

int start = 0;
int end = max;
while(start <= end) {
    int mid = (start + end) / 2;
    if(solve(mid) > m) {
        end = mid - 1;
    }
    else {
        start = mid + 1;   
    }
}
bw.write(end + "");

 

하지만 두번째 방법이 생각나서 이 글을 작성해본다.

일반적으로 공평하게 받을 수 있는 상한액 = 총 예산 / 지방의 수 = m / n
만약에 총 예산이 요청한 예산들의 합보다 크면
    → 요청한 예산 중 최댓값만큼 상한액을 설정하면 된다.
총 예산이 요청한 예산들의 합보다 작으면
    → 공평하게 받을 수 있는 상한액에서 1씩 증가하며 배정된 예산을 계산해본다.
    → 배정된 예산이 총 예산보다 커지면 멈춘다.

 

이를 코드로 구현하면 아래와 같다.

if(sum <= m) {
    bw.write(max + "");
}
else {
    int current = m / n;
    while(true) {
        if(solve(current) > m) break;
        current++;
    }

    bw.write(current - 1 + "");
}

 

결과를 비교해보면 이분탐색을 사용한 방법이 효율적이다.

이분탐색을 통해 찾아가는 방법은 구간에서 중간값을 찾아서 탐색하므로 평균적인 시간이 걸릴 것이다.

하지만 내가 두번째로 생각한 방식은 최솟값과 구하고자 하는 값의 차이가 작을 때 효율적일 것이다.

4
1 1 1 500
500

위와 같은 입력이 들어왔을 경우 125부터 1씩 증가하며 497을 구하게 된다.

이처럼 값들의 차가 클 경우 입력이 길어질수록 오래 걸릴 수 있다.

 

모두 맞는 풀이지만 효율성을 따지면 이분탐색이 적합하다.

---

🍀 풀이 🍀

1️⃣ 이분탐색 풀이

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

public class Main {
    static int[] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        requests = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int max = 0;
        for(int i = 0; i < n; i++) {
            requests[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, requests[i]);
        }

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

        int start = 0;
        int end = max;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(solve(mid) > m) {
                end = mid - 1;
            }
            else {
                start = mid + 1;   
            }
        }
        bw.write(end + "");
        bw.flush();
        bw.close();
    }

    static int solve(int current) {
        int answer = 0;
        for(int i = 0; i < requests.length; i++) {
            answer += current >= requests[i] ? requests[i] : current;
        }
        return answer;
    }
}

2️⃣ 가능한 상한액 중 최소를 계산 후 최댓값 구하기

package Baekjoon;

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

public class BinarySearch2512 {
    static int[] requests;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        requests = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        int sum = 0;
        int max = 0;
        for(int i = 0; i < n; i++) {
            requests[i] = Integer.parseInt(st.nextToken());
            sum += requests[i];
            max = Math.max(max, requests[i]);
        }

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

        if(sum <= m) { //요청 예산의 합이 전체 예산보다 작을 경우
            bw.write(max + ""); //가장 요청이 큰 액수에 맞춘다.
        }
        else {
            int current = m / n; //공평하게 나눴을 경우부터 탐색
            while(true) {
                if(solve(current) > m) break;
                current++;
            }

            bw.write(current - 1 + "");
        }
        bw.flush();
        bw.close();
    }

    static int solve(int current) {
        int answer = 0;
        for(int i = 0; i < requests.length; i++) {
            answer += current >= requests[i] ? requests[i] : current;
        }
        return answer;
    }
}