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

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

2512번: 예산

코드설명

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

기존의 이진 탐색 문제와의 구현은 유사하지만, 개념의 차이가 존재합니다.

 

이진탐색과 파라매트릭 서치의 차이점에 대해 알아보겠습니다.

• 이진탐색은 정렬된 값들이 주어졋을때, 그 값들 중 원하는 값을 찾습니다. 이진탐색은 정렬된 데이터 위에서만 유효합니다.
• 파라메트릭 서치는 주어진 범위 내에서 원하는 값 혹은 조건에 일치하는 값을 찾아냅니다. 조건에 부합하는 값을 찾는 것이기에, 정렬된 데이터가 아니라도 상관없습니다.

주어진 최적화 문제를 파라매트릭 서치를 활용해서 풀기 위해 결정 문제로 바꾸어 보겠습니다.

최적화 문제 : 정해진 총액(M) 이하에서 최대 예산을 받기 위해서 설정해야하는 최대의 상한액(K)은 얼마인가?

결정문제 : 정해진 총액(M) 이하에서 최대 예산은 최대의 상한액(K) 이하가 되도록 할 수 있는가?

 

위의 조건들을 기반으로 작성합니다.

 

문제에서 제가 틀렸던 부분은, 총 예산을 끝시작점으로 잡은점입니다.

paramatricSearch(0, M); // M : 총 예산

대신에,

for(int i=0;i<N;i++) {
    arr[i] = Integer.parseInt(st.nextToken());
    end = Math.max(end, arr[i]);
}

end값을 주어진 원소값 중 최대값으로 설정해야합니다.

 

이러한 end값으로 처리해야하는 이유는, 

현재 예산 값으로 설정할경우, 항상 sum 값이 middle 값보다 작기 때문에 계속해서 예산이 늘어납니다.

end값을 통해 주어진 원소값 중 최대값으로 설정하여 더 작은 값에서 최대값을 찾도록 설정해야만 올바르게 파라매트릭 서치가 진행됩니다.

 

주석으로 코드에 자세한 설명을 작성해보았습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M, K = 0;
	public static int[] arr;
	public static int answer = 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());
    	int end = 0;
    	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(0, end);
    }
    
    public static void paramatricSearch(int start, int end) {
    	int left = 0; //배정예산 시작점
    	int right = end; //배정예산 끝점
    	
    	while(left <= right) {
    		int middle = ( left + right ) / 2; //배정예산 계산.
 
    		int sum = 0;
    		for(int i=0;i<N;i++) {
    			if(middle >= arr[i]) { //배정예산이 더 크다면, arr[i]만큼만 사용하면 됩니다.
    				sum += arr[i]; //사용한만큼 더합니다.
    			}else if(middle < arr[i]) { //사용해야하는 금액이 더 크다면, 
    				sum += middle; //배정된 예산만큼만 사용합니다.
    			}
    		}
//    		System.out.println("middle:"+middle+"sum:"+sum);
    			
    		//만약 사용금액이 M보다 작다면, 예산을 더 늘려도 됩니다.
    		if(sum <= M) {
    			left = middle + 1;
    		}
    		//만약 사용금액이 M보다 크다면, 예산을 줄여야야합니다.
    		else if(sum > M) {
    			right = middle - 1;
    		}
    	}
    	System.out.println(right);
    }
    
}

 

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;
    		}
    	}
    	
    }
 
}

 

 

정답코드 3 입니다.

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;
	}
 
}