[BOJ / C++] 랜선 자르기 (이분탐색, Parametric Search)

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

 

1. 코드

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

using ll = long long;

bool solve(vector<int>& arr, int k, int n, ll x) {
    ll cur = 0;
    for (int i = 0; i < k; i++) cur += arr[i] / x;
    return cur >= n;
}

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

    int k, n;
    cin >> k >> n;

    vector<int> arr(k);
    for (int i = 0; i < k; i++) cin >> arr[i];

    ll st = 1;
    ll en = 0x7fffffff; // 2^31-1
    while (st <= en) {
        ll mid = (st+en)/2;
        if (solve(arr, k, n, mid)) st = mid+1;
        else en = mid-1;
    }
    cout << en;
}

 

 

2. 시간복잡도

k = 10,000, n = 1,000,000이다. Parametric Search를 하는데 탐색 구간은 [1, 2^31-1]이고 이진탐색에 lgn이 소요되므로 lg2^31 = 31이다. 한번의 이진탐색당 k번 loop를 반복하니 시간복잡도는 O(k)이다.

따라서 전체 시간복잡도는 O(k * lg2^31)이고 310,000 < 10^8 이므로 시간제한 1초 내에 통과 가능하다.

 

 

3. 분석

* Parametric Search란?

: 조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정문제로 변환해 이분탐색을 수행하는 방법이다.

 

이 문제에서는 이렇게 적용된다.

(최적화 문제) N개를 만들 수 있는 랜선의 최대 길이

(결정 문제) 랜선의 길이가 r일 때 랜선이 N개 이상인가 아닌가?

 

이렇게 (최적화 문제)를 (결정문제)로 바꾸고 길이의 전체 범위 [1, 2^31-1]에서 랜선 길이가 최대가 되는 upper_bound 지점을 이분탐색으로 찾아내면 된다.