파라메트릭 서치

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것이다.

다음 문제를 보자.

파라메트릭 서치로 풀 수 있는 문제의 알고리즘은 다음과 같다.

1. 조건을 만족하는 값들을 이분 탐색
2. 만족하는 값들을 재귀적으로 이분탐색
3. 만족하는 값 중에서 최대값을 발견하면 종료

이 알고리즘으로 문제를 풀어보면 다음과 같다.

만약 mid 값으로 잘랐을 때 m개 이상을 만족하면 뒷 부분 탐색,

만족하지 않는 다면 앞 부분 탐색을 진행하였다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MAX 1000000
typedef long long ll;
using namespace std;

int n,m;
int heights[MAX];
int ans=0;

int main(){
	cin >> n >> m;
	for(int i=0;i<n;i++){
		cin >> heights[i];
	}
	int s=0;
	int e=1000000000;
	while(s<=e){
		ll total=0;
		int mid=(s+e)/2;
		for(int i=0;i<n;i++){
			if(heights[i]>mid) total+=heights[i]-mid;
		}
		if(total<m){
			e=mid-1;
		}
		else{
			ans=max(ans,mid);
			s=mid+1;
		}
	}
	cout << ans;
}

출처 : 이것이 취업을 위한 코딩테스트다