[BOJ / C++] 과자 나눠주기 (이분탐색, Parametric Search)

문제링크: https://www.acmicpc.net/problem/16401

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

bool possible(vector<int>& snack, int len, int m) {
    ll num = 0;
    for (int i = 0; i < snack.size(); i++) {
        num += snack[i] / len;
    }
    return num >= m;
}

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

    int m, n;
    cin >> m >> n;

    vector<int> snack(n);
    for (int i = 0; i < n; i++) {
        cin >> snack[i];
    }

    ll st = 0;
    ll en = 0x7fffffff;
    while (st <= en) {
        ll mid = (st + en) / 2;
        
        if (mid == 0) {
            cout << 0;
            return 0;
        }

        if (possible(snack, mid, m)) st = mid+1;
        else en = mid-1;
    }

    cout << en; 
}

 

 

2. 시간복잡도

Parametric Search를 사용해야한다. 과자의 길이 전 범위에서 이분탐색을 진행한다. len = 1,000,000,000이므로 lg(len) = 30이고, 나눠지는 갯수가 몇개인지 세는데 O(n)이 걸리므로 n = 1,000,000이고, O(nlg(len)) = 1,000,000 * 30 = 30,000,000 < 10^8 이므로 시간제한 1초 안에 통과 가능하다.

 

 

3. 분석

Parametric Search 문제이다. 

while (st <= en) {
    ll mid = (st + en) / 2;
    if (possible(snack, mid, m)) st = mid+1;
    else en = mid-1;
}

 

이렇게 하면 st==en까지 possible의 범위의 upper bound에 오고 마지막에 st = mid + 1이 되면서 en이 마지막 possible이 된다. 

 

문제 조건에서 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없으면 0을 출력하라는 조건이 있는데 해당 부분 처리를 위해 mid == 0 이 면 0을 출력하고 종료되게했다. 이런 처리를 하지 않으면 possible 함수에서 zero divide로 인한 런타임에러가 발생한다.