[백준] 2512 예산 - 파라메트릭 서치(Paramatric Search) JAVA

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

2512번: 예산

코드설명

파라메트릭 서치 문제입니다.

 

기본적인 구현은 이분탐색과 비슷하지만, 이분탐색의 경우 정렬된 값을 활용하여 진행합니다.

반면에, 파라메트릭 서치는 정렬된 경우가 아닌, 문제에서 나온 문제의 최소값과 최대값을 구하여 진행합니다.

 

코드에 대한 설명을 해보겠습니다.

4
120 110 140 150
485

 

 

구해야하는 것은, 485 ( 정부의 최대 예산 )보다 작거나 같게하여, 각 지방정부의 요청한 예산을 배정합니다.

 

문제 조건을 보면, 

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.

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

 

위의 조건을 통하여 정수 상한액 보다 작을경우 그대로 배정한다는 것을 알 수 있습니다.

 

이제 적절한 예산을 찾기 위한 로직입니다.

start = 0, end = 150 으로 설정합니다.

middle = ( 0 + 150 ) / 2;  ( middle 이분탐색과 같은 구현으로써 이를 통해 O(logN)의 시간복잡도를 가집니다. )

 

이제 120, 110, 140, 150 을 순회하면서 각 지방이 요청한 예산과 middle = 75  를 비교합니다.

120 > 75 이므로, 지방정부가 정수상한액 보다 더 많이 요청했습니다. 그러므로 answer += 75 입니다.

110 > 75 이므로, 지방정부가 정수상한액보다 더 많이 요청했습니다. 그러므로 answer += 75 입니다.

140 > 75 이므로, 지방정부가 정수상한액보다 더 많이 요청했습니다. 그러므로 answer += 75 입니다.

150 > 75 이므로, 지방정부가 정수상한액보다 더 많이 요청했습니다. 그러므로 answer += 75 입니다.

총 answer = 300 입니다. answer이 485 보다 작으므로, 아직 예산이 남았습니다. 우리는 예산의 범위 안에서 최대의 예산을 설정해야합니다.

또한, 여전히 start <= end이기에( end가 start보다 작은 경우가 나오는 순간이 end와 start가 같아지면서 해당 값을 찾게 됨) 계속해서 진행됩니다.

 

그러므로, start = middle + 1 로 설정하여,

start = 76, end = 150 으로 설정합니다.

middle = (76 + 150) / 2; == 113 

이제 위의 과정과 같이

이제 120, 110, 140, 150 을 순회하면서 각 지방이 요청한 예산과 middle = 113  과 비교합니다.

똑같이 진행하면,  answer = 449 가 됩니다.

answer < K 보다 작은경우이므로, start = 113 + 1 = 114 가 되고, 다시 같은 과정을 반복합니다.

 

계속해서 진행하다보면, start와 end가 같아지는 지점이 찾아오면서, 위의 조건이 만족하게 됩니다.

 

문제의 예산 안에서 최대값을 구하기 위해서는 아래의 조건문처럼 사용해야만 합니다.

if(answer <= M) { //예산요청의 양이 M보다 작거나 같을경우 최대값을 찾아야하니, 예산의 양을 더 크게하기 위해 start를 증가시킴, 작거나 같은경우로 처리해야 최대값을 구합니다.
    start = middle + 1;
}else { //예산요청의 양이 M보다 클경우, 예산을 줄여야되니 줄입니다.
    end = middle - 1;
}

 

코드

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


public class Main {
	
	public static int N,M;
	public static int[] arr;
	public static int answer = 0;
	public static int start = 0, end = 0;
    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()); // 여러 지방의 예산 요청
    		end = Math.max(end, arr[i]);
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	paraMatricSearch();    	
    	System.out.println(end);
    }
    
    public static void paraMatricSearch(){
    	
    	while(start <= end) { //각 예산들의 최대값을 구하는 점
    		
    		int middle = (start + end) / 2; //평균 예산
    		answer = 0; //지방정부들에 줄 수 있는 예산의 합
    		for(int i=0;i<N;i++) {
    			if(arr[i] > middle) answer += middle; //평균 예산보다 더 많은 예산을 요청한 경우 평균 예산만 분배 
    			else answer += arr[i]; //평균 예산안의 범위에 있을 경우 지방정부가 요청한 만큼 줍니다.
    		}

    		if(answer <= M) { //예산요청의 양이 M보다 작거나 같을경우 최대값을 찾아야하니, 예산의 양을 더 크게하기 위해 start를 증가시킴, 작거나 같은경우로 처리해야 최대값을 구합니다.
    			start = middle + 1;
    		}else { //예산요청의 양이 M보다 클경우, 예산을 줄여야되니 줄입니다.
    			end = middle - 1;
    		}
    	}
    	
    }

}

 

정답코드 2입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K, M;
	public static int answer = 0;
	public static int[] arr;
	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());
		int maxRequest = 0;
		for(int i=0;i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			maxRequest = Math.max(maxRequest, arr[i]);
		}
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		System.out.println(optimize(1, maxRequest));
	}
	
	public static int optimize(int lo, int hi) {
		int left = lo - 1, right = hi + 1;
		while(left + 1 < right) {
			int mid = (left + right) / 2;
			if(decision(mid) == true) {
				left = mid;
			} else if(decision(mid) == false) {
				right = mid;
			}
		}
		return right - 1;
	}
	
	public static boolean decision(int maxBudget) {
		int ret = 0;
		for(int i=0; i<N; i++) {
			if(arr[i] >= maxBudget) {
				ret += maxBudget;
			}else {
				ret += arr[i];
			}
		}
		return ret <= M;
	}

}