[백준 1654번] [이분 탐색] 랜선 자르기

가장 쉽게 생각할 수 있는 것은 브루트 포스이다.(전부 다 해보는 것)

Brute force방법으로 하기 위해서는 숫자를 작은 것부터 계속해서 숫자를 키워나가면서 각 랜선을 해당 숫자로 나눈 몫의 합이 n보다 크거나 같으면 계속해서 숫자를 키워나가다가 n보다 작은 타이밍이 오면 그 직전까지의 숫자를 출력하는 방식으로 이해할 수 있다.

 

다만, 이 방식으로 진행하게 되면 시간초과가 나게 된다.

왜냐하면, 고려해야할 숫자의 범위가 maximum이 최대 랜선의 길이 x k(랜선의 숫자만큼 몫을 구해야하므로)가 된다.

이때 시간제한이 2초이므로 대략 10^8 * 2의 연산을 훨씬 초과한다. 즉, 단순히 연산하는 방식으로는 처리할 수 없음을 파악할 수 있다.

 

그 다음으로 생각할 수 있는 것은 이분탐색이다.

이분탐색을 생각할 수 있는 근거는 만족하는 범위가 연속적이기 때문이다.

즉, 만들 수 있는 랜선의 갯수의 범위가 연속적이기 때문에 파라메트릭 서치 방법 중 하나인 이분탐색으로 정답을 도출 할 수 있게 된다.

 

위의 방법을 활용한 코드는 다음과 같다.

 

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void){
    int k, n;
    cin >> k >> n;
    int value_store[k];
    for (int i = 0; i < k; i++){
        cin >> value_store[i];
    }

    int max_value = * max_element(value_store, value_store + k);

    long long start = 1;
    long long end = max_value;

    while (end - start > 1){
        int mid = (start + end) / 2;
        long long sum = 0;
        
        for (int i = 0; i < k; i++){
            sum += value_store[i] / mid;
        }
        
        if (sum >= n){
            start = mid;
        }
        else end = mid - 1;
    }

    long long final_check = 0;

    for(int i = 0; i < k; i++){
        final_check += value_store[i] / end;
    }

    if (final_check >= n) cout << end << "\n";
    else cout << start << "\n";

    return 0;
}

 

이 문제에서 사실 가장 중요하게 생각해야 할 것은 랜선의 길이의 범위이다.

이 숫자는 매우 큰 숫자이므로 long long 형을 받아야 한다는 것이다. 항상 어느 자료형을 사용해야 하는지 조심하는 습관을 가지도록 노력하자.