파라메트릭 서치 (Parametric Search)

관련 문제

문제	난이도	핵심
1654번 — 랜선 자르기	실버 II	최대 길이 구하기
2805번 — 나무 자르기	실버 II	최소 높이 구하기
2512번 — 예산	실버 II	상한액 결정
11662번 — 민호와 강호	골드 V	실수 이분탐색

---

1. 개념

파라메트릭 서치(Parametric Search)란, 최적화 문제를 결정 문제로 바꿔서 이분탐색으로 푸는 기법이다.

"정답이 될 수 있는가?"를 반복해서 물어, 최적값을 좁혀간다.

직접 정답을 구하기 어려울 때, 특정 값 mid가 조건을 만족하는지만 판단한다.
그 판단 결과(true/false)가 단조적(monotone)이면 이분탐색이 적용된다.

---

2. 동작 과정

예시: 나무를 M미터 이상 얻으려면 절단기 높이 H를 최대 얼마로 설정할 수 있는가?

나무 = [20, 15, 10, 17], M = 7

단계	lo	hi	mid	획득량	조건(≥7)	이동
1	0	20	10	7+5+0+7=15	✅	lo = 11
2	11	20	15	5+0+0+2=7	✅	lo = 16
3	16	20	18	2+0+0+0=2	❌	hi = 17
4	16	17	16	4+0+0+1=5	✅	lo = 17
5	17	17	—	종료	—	—

최종 높이: 15 (lo가 수렴한 마지막 ✅ 값)

---

3. 핵심 포인트 2가지

결정 함수(isOk)가 단조여야 한다

파라메트릭 서치의 전제 조건이다.
어떤 값 x에서 조건이 만족되면, x보다 작은(또는 큰) 모든 값도 일관되게 만족/불만족해야 한다.

• 높이가 낮을수록 → 획득량 증가 → 조건 만족 가능성 ↑
• 높이가 높을수록 → 획득량 감소 → 조건 만족 가능성 ↓

이 단조성이 없으면 이분탐색을 적용할 수 없다.

lo / hi 수렴 조건과 경계 처리

lo < hi 또는 lo <= hi 중 문제에 맞게 선택해야 하며, 실수하면 무한루프 또는 오답이 난다.

• 최댓값 구하기 → 조건 만족 시 lo = mid + 1, 종료 후 hi 반환
• 최솟값 구하기 → 조건 불만족 시 hi = mid - 1, 종료 후 lo 반환

---

4. 코드

long lo = 0, hi = MAX;

while (lo <= hi) {
    long mid = (lo + hi) / 2;

    if (isOk(mid)) {   // mid가 조건을 만족하는가?
        lo = mid + 1;  // 더 큰 값도 가능한지 탐색 (최댓값 구할 때)
    } else {
        hi = mid - 1;  // 줄여야 함
    }
}

// 최댓값: hi, 최솟값: lo

isOk(mid) 함수만 문제에 맞게 구현하면 된다.
탐색 범위(lo, hi)는 정답의 후보 범위로 설정한다.

---

5. 시간복잡도

방법	시간복잡도
완전 탐색 (모든 후보값 시도)	O(MAX × N)
파라메트릭 서치	O(N log MAX)

탐색 범위 MAX = 2,000,000,000이라도 log₂(2×10⁹) ≈ 31이므로 결정 함수만 빠르면 충분히 통과한다.

---

6. 주의사항

• 탐색 범위를 int로 잡으면 오버플로우가 난다. lo, hi, mid는 long으로 선언하라.
• 획득량 합산도 long으로 받아야 한다. 나무 수 × 최대 높이는 int 범위를 쉽게 초과한다.
• 최댓값 문제는 hi를 반환, 최솟값 문제는 lo를 반환한다. 헷갈리면 수렴 직전 상태를 직접 추적해보라.
• isOk 함수의 단조성을 먼저 검증하고 코드를 짜라. 단조성이 없으면 파라메트릭 서치 자체가 적용 불가다.
• mid = (lo + hi) / 2도 오버플로우 위험이 있다. long이면 괜찮지만 습관적으로 lo + (hi - lo) / 2도 고려하라.