3. 파라메트릭 서치 이해하기

• 이진탐색 조건: 변경할(최적화할) 값 x에 대하여 f(x)가 단조 증가 혹은 단조 감소
• 단조 증가 함수 : x<=y 이면 f(x)<=f(y)인 경우
• 일반적으로 조건(constraint)은 f(x)에 대하여 정의된다.

1. 파라메트릭 서치(Parametric Search)란?

• 최적화 문제를 결정 문제(예 혹은 아니오) 로 바꾸어 해결하는 기법
• 일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

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

2512번: 예산

let fs = require("fs");
let input = fs.readFileSync("index.txt").toString().split("\n");

let n = Number(input[0])// 지방의 수
let arr = input[1].split(" ").map(Number); // 각 지방의 예산 요청
let m= Number(input[2])//총 예산

let start=1 // 이진 탐색을 위한 시작점(start)과 끝점(end) 설정
let end = arr.reduce((a,b)=>Math.max(a,b));//가장 큰 수

let result = 0 ;

while(start<=end){
    //이진탐색 수행(반복문)
    let mid = parseInt((start+end)/2)
    let total = 0 // 배정된 예산의 총액 계산
    for(x of arr){
        total=total+Math.min(x,mid)
    }
    if(total<=m){
        result=mid;
        start=mid+1
    }else{
        end=mid-1
    }
}
console.log(result)