[백준] 15732번: 도토리 숨기기 - 왜 이분탐색인가?

입력 조건을 보자.

• 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다.

가장 쉽게 떠올릴 수 있는 방식은?

1. 브루트포스이다. 하나의 규칙에 대해 N개의 상자를 모두 돌면서 개수를 세야하니 O(NK)가 되어서 시간초과가 된다.

O(NK)가 문제이고... k개의 규칙에서 상자 순회가 존재해서는 안된다는 뜻이다.

그런데 하나의 규칙을 보면 [a, b]에서 간격 c로 도토리를 넣을 때 a~b 구간의 총 도토리 개수는 O(1)로 구할 수 있다.

수식은 대충 (b-a)/c + 1 정도가 되겠다.

 

그럼 k개의 규칙에 대해 O(k)로 구간 [1, n]에 대해서 총 도토리 개수를 구할 수 있는 것이다. 이제 가닥이 좀 잡히는데, 매개변수 탐색을 쓰면 될 것 같다. 그 근거는 다음과 같다.

• 총 도토리의 개수는 구간과 비례해서 선형적으로 증가한다. 여기서 구간이란 답이되는 변수를 말한다. 따라서 매개변수 탐색을 쓸 수 있다. 매개변수는 구간 = 답이 되는 변수로 설정하면 된다.
• 구간 mid에 대해 1~mid의 도토리 개수는 O(k)로 구할 수 있다. 
• 이분 탐색으로 구간을 구한다면 전체 시간 복잡도는 O(k log n) 이므로 효율성은 통과!

그대로 구현해주면 된다. 그런데 이분 탐색, 매개변수 탐색 문제는 다음 경우에 따라 구현에 실패하는 경우가 종종 있었다.

1. mid = (st+en)/2 or mid = (st+en+1)/2
2. while(st<en) or while(st<=en)
3. st=mid or st=mid-1

1번 조건은 upper인지 lower인지에 달려있다. 가령 FFFTTT 배열에서 첫 번째 T의 인덱스를 찾는 lower bound는 내림으로 mid를 구하는 것을 추천한다.

3번째는 문제가 요구하는 것에 따라 mid와 그 오른쪽이 답이 되는지, mid가 포함이 되는지 그런걸 잘 따져보면 되고 2번은 하나로 고정해서 쓰면 될 것 같다. 아래는 간단하게 AI를 돌려 정리한 내용이다.

 

그 전에!!! 답 부터...

/** 파라미터 서치 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, k, d;
int rules[10005][3]; // A번부터 B번까지 C의 간격

long long count_(int box)
{
    // 1~box까지 도토리 개수 구하기
    long long rt = 0;
    for (int i = 0; i < k; i++)
    {
        long long a = rules[i][0], b = rules[i][1], c = rules[i][2];
        if (a > box)
            continue;
        // a~b까지 간격 c
        b = min(box, (int)b); // b가 box보다 크면 안됨. box까지만 탐색해야함.
        rt += (b - a) / c + 1;
    }
    return rt;
}

int func()
{
    // 파라미터릭 서치로 1~mid의 범위에 도토리를 모두 넣으며 개수를 구함.
    // 구한 개수가 cnt라 했을 때 cnt가 d보다 작다면 mid+1~en에 대해 다시 mid 갱신
    // cnt가 d보다 같거나 크다면 st~mid에 대해 다시 mid 갱신
    int st = 1, en = n;
    while (st < en)
    {
        int mid = (st + en) / 2;
        if (count_(mid) >= d)
            en = mid;
        else
            st = mid + 1;
    }
    return st;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> d;
    for (int i = 0; i < k; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        rules[i][0] = a;
        rules[i][1] = b;
        rules[i][2] = c;
    }

    cout << func();
}

 

1. Lower Bound (최솟값 찾기)

목표: 조건을 만족하는 값들 중 가장 작은 값을 찾는 것. (e.g., [F, F, F, T, T, T] 배열에서 첫 번째 T의 인덱스 찾기)

while (st < en) {
    int mid = (st+en) / 2; // ⭐️ 중간값 (내림)

    if (decision(mid)) { // mid가 조건을 만족하는가? (T)
        // mid가 답일 수 있으니, mid를 포함하여 왼쪽 구간을 다시 탐색
        en = mid;
    } else { // mid가 조건을 만족하지 못하는가? (F)
        // mid와 그 왼쪽은 절대 답이 될 수 없으므로, 오른쪽 구간을 탐색
        st = mid + 1;
    }
}
// 루프 종료 시 st와 en은 같은 값을 가짐
return st;

로직 분석

• decision(mid)가 참이면, mid가 정답일 수 있지만 더 작은 정답이 [st, mid] 구간에 있을 수 있으므로 en = mid로 범위를 좁힙니다. mid를 버리지 않는 것이 핵심입니다.
• decision(mid)가 거짓이면, mid는 확실히 답이 아니므로 [mid + 1, en] 구간만 탐색하면 됩니다.

---

2. Upper Bound (최댓값 찾기)

목표: 조건을 만족하는 값들 중 가장 큰 값을 찾는 것. (e.g., [T, T, T, F, F, F] 배열에서 마지막 T의 인덱스 찾기)

while (st < en) {
    int mid = (st+en+1) / 2; // ⭐️ 중간값 (올림)

    if (decision(mid)) { // mid가 조건을 만족하는가? (T)
        // mid가 답일 수 있으니, mid를 포함하여 오른쪽 구간을 다시 탐색
        st = mid;
    } else { // mid가 조건을 만족하지 못하는가? (F)
        // mid와 그 오른쪽은 절대 답이 될 수 없으므로, 왼쪽 구간을 탐색
        en = mid - 1;
    }
}
// 루프 종료 시 st와 en은 같은 값을 가짐
return st;

로직 분석

• decision(mid)가 참이면, mid가 정답일 수 있지만 더 큰 정답이 [mid, en] 구간에 있을 수 있으므로 st = mid로 범위를 좁힙니다.
• decision(mid)가 거짓이면, mid는 확실히 답이 아니므로 [st, mid - 1] 구간만 탐색하면 됩니다.
• 가장 중요한 점: st = mid 로직 때문에 mid를 계산할 때 **반드시 올림(+1)**을 해야 합니다. 그렇지 않으면 무한 루프에 빠질 수 있습니다. (아래에서 자세히 설명)

---

무한 루프 방지

무한 루프는 탐색 범위가 더 이상 줄어들지 않을 때, 특히 st와 en이 딱 1 차이 날 때 발생합니다. 코드를 짜면서 바로 검증할 수 있는 방법은 다음과 같습니다.

2단계 정신적 시뮬레이션

1. st = k, en = k + 1인 최악의 상황을 가정합니다.
2. mid를 계산하고, if와 else 분기 모두에서 st가 증가하거나 en이 감소하는지 확인합니다.

예시 1: Upper Bound 템플릿에서 mid를 잘못 계산한 경우

• 상황: st = 5, en = 6
• 잘못된 코드: int mid = (st + en) / 2; // 올림 안 함
• 시뮬레이션:
  • mid = (5 + 6) / 2 = 5가 됩니다.
  • if (decision(5))가 true라면? → st = mid가 실행되어 st는 여전히 5입니다.
  • 결과: st=5, en=6 상태가 변하지 않으므로 무한 루프에 빠집니다. ❌
• 올바른 코드: int mid = (st + en + 1) / 2;
• 시뮬레이션:
  • mid = (5 + 6 + 1) / 2 = 6이 됩니다.
  • if (decision(6))가 true라면? → st = mid 실행, st가 6이 됨 → st와 en이 같아져 루프 종료.
  • if (decision(6))가 false라면? → en = mid - 1 실행, en이 5가 됨 → st와 en이 같아져 루프 종료.
  • 결과: 어떤 경우든 범위가 좁혀지므로 안전합니다. ✅

예시 2: Lower Bound 템플릿 검증

• 상황: st = 5, en = 6
• 코드: int mid = (st + en) / 2;
• 시뮬레이션:
  • mid = (5 + 6) / 2 = 5가 됩니다.
  • if (decision(5))가 true라면? → en = mid 실행, en이 5가 됨 → st와 en이 같아져 루프 종료.
  • if (decision(5))가 false라면? → st = mid + 1 실행, st가 6이 됨 → st와 en이 같아져 루프 종료.
  • 결과: 안전합니다. ✅