BOJ 1654. 랜선자르기

문제

코드

#include <iostream>
#include <vector>

using namespace std;
vector<int> v;
int main(int argc, char const *argv[])
{
    long n, k, ans = 0;
    long long maxVal = 0, left = 0, mid = 0, right = 0;
    int nums;
    cin >> n >> k;

    for (int i = 0; i < n; i++)
    {
        cin >> nums;
        v.push_back(nums);
        if (maxVal < nums)
        {
            maxVal = nums;
        }
    }

    left = 1, right = maxVal;

    while (left <= right)
    {
        int temp = 0;
        mid = (right + left) / 2;
        cout << mid << endl;
        for (int i = 0; i < v.size(); i++)
        {
            temp += v[i] / mid;
        }

        if (temp < k)
        {
            right = mid - 1;
        }
        else
        {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

• 이분탐색에서 특정값이 제시되고 그 값을 찾는 원리를 알고 있었지만, 특정값이 제시되지 않는 상황에서 적절한 값을 찾아가는 이분탐색은 이해하기 어려웠다.
• 랜선 자체를 나누는 일은 맞는데,기준을 무엇으로 하느냐가 고민거리였다.
  결국 각각의 랜선을 나눌 값들을 구하기 위한 탐색작업이였고, 11이 나오는 값인 200이 출력된 것이다.

할만하다고 생각했던 이분탐색이 골치를 썩일줄이야.. 😨