[BOJ] 2512 예산 (Java)

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

 

이 문제의 경우 예산액의 범위가 1 이상 100,000 이하여서 굳이 이분탐색이진 않아도 될 거 같긴 하다만, 이분탐색으로 풀었음.

지방 예산액과 총 예산액이 주어졌을 때, 해당 총 예산액을 만족하는 최대 예산 상한액을 구하는 문제.

그렇다면 이 최대 예산 상한액을 m으로 두고 1 ~ 최대 지방 예산액 사이에서 조건을 만족하는 m 값을 구하면 된다.

조건을 만족하는 지 확인하는 코드는 다음과 같다.

 

// 총 예산 계산
int sum = 0;
// 모든 지방의 예산의 예산 상한액보다 작을 경우 idx의 default값은 n이어야 함
int idx = n;

// 1. 현재 예산 상한액(m) 보다 작은 지방 예산의 합 = arr[i]원
for(int i=0; i<n; i++) {
	if(arr[i] <= m) sum += arr[i];
	else {
		idx = i;
		break;
	}
}

// 2. 현재 예산 상한액(m) 보다 큰 지방 예산의 합 = m원 으로 일정
sum += m * (n - idx);

 

이렇게 이분탐색 과정 중 현재 상한액인 m 값에 따라 계산해주면 되는데,

지방 예산액이 들어있는 arr을 돌며 현재 m 값보다 작거나 같으면 해당 지방 예산액 arr[i]를 더해주고, 크면 상한액인 m을 더해준다.

그리고 이 sum을 가지고 총 예산액과 비교하면 되는데, 이때!! idx의 초기값을 생각없이 0으로 둬서 틀렸었는데, 주석과 같은 이유로 n이 되어야 한다.

 

최종 제출 코드는 아래와 같다.

package BOJ;

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

public class BOJ_2512 {

    static int n;
    static int ans;
    static int[] arr;

    public static void binarySearch(int s, int e, int target){
        if(s > e) return;
        int m = (s + e) / 2;
        // 총 예산 계산
        int sum = 0;
        // 모든 지방의 예산의 예산 상한액보다 작을 경우 idx의 default값은 n이어야 함
        int idx = n;
        // 현재 예산 상한액(m) 보다 작은 지방 예산의 합 = arr[i]원
        for(int i=0; i<n; i++) {
            if(arr[i] <= m) sum += arr[i];
            else {
                idx = i;
                break;
            }
        }
        // 현재 예산 상한액(m) 보다 큰 지방 예산의 합 = m원 으로 일정
        sum += m * (n - idx);
        // 총액보다 작거나 같은경우
        if(sum <= target){
            ans = m;
            binarySearch(m+1, e, target);
        // 총액보다 큰경우
        }else binarySearch(s, m-1, target);
    }

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

        n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int target = Integer.parseInt(br.readLine());
        // start: 1원, end: 지방 예산액 중 최댓값
        binarySearch(1, arr[n-1], target);
        System.out.println(ans);
    }
}