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

 

 

 

문제를 처음 접했을 때, 이걸 어떻게 하라는 건가 싶었다.

 

#include <iostream>
using namespace std;
 
int k, n;
unsigned long long int arr[10000];
 
int counted;
 
bool cutting(int standard)
{
    counted = 0;
 
    for (int i = 0; i < k; i++)
    {
        unsigned long long int temp = arr[i];
        while (temp >= standard)
        {
            temp -= standard;
            counted++;
        }
    }
    if (counted >= n)
        return true;
    else
        return false;
}
 
int main(void)
{
    cin >> k >> n;
    for (int i = 0; i < k; i++)
        cin >> arr[i];
 
    unsigned long long int left, mid, right;
 
    left = 0;
    right = -1;
    
    unsigned long long int ans = 0;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (cutting(mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
 
    cout << ans;
}

 

느낀 점

 

매우 좋은 문제라고 생각이 드는 게, 이진 탐색 자체를 일종의 parameter로 써서 진행한다는 점이, 이진 탐색의 활용도를 훨씬 높여줄 수 있음을 증명한다.

그냥 이진탐색이라고 한다면, 일직선상의 정수 범위에서 계산을 진행하는 것처럼 느껴질 수 있는데,

이런 방식을 쓰면 다양한 방정식이 이진 탐색을 도입할 수 있게 된다.

문제 자체의 어려움보다, 사고를 비트는 게 더 어려웠다.