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

#include <iostream>
using namespace std;
 
int k, n;
// 문제에서 요구하는 랜선의 개수를 n이라고 하고,
unsigned long long int arr[10000];
// arr 배열은 처음에 주어진 초기 랜선의 길이들이다.
 
int counted;
// 잘라진 숫자인 counted는 n과 같거나 많아야 한다.
// 처음에는 같으면 될 줄 알았는데, 그렇게 해버리면 더 많이 잘리는 경우를 고려 못한다.
// 항상 정확한 개수로 잘리는 게 아니다!
 
bool cutting(int standard)
{
    // 매개변수로, 자르고자 하는 길이 값을 가져온다.
    counted = 0;
    // 일단 counted를 초기화한 다음에,
 
    for (int i = 0; i < k; i++)
    {
        unsigned long long int temp = arr[i];
        // 초기 랜선 길이 1개씩 가져다가,
        while (temp >= standard)
        {
            temp -= standard;
            counted++;
            // 더 이상 자를 수 없을 때까지 자르면서 count 한다!
        }
    }
    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;
    // 아래에 left와 right를 비교하여 left가 작으면 진행하는 while문이 있다.
    // 그러면 이게 왜 작동하는가 의문이 들 수 있는데, 간단하다.
    // 내가 선언할 때에 unsigned로 선언하였기 때문에 -1은 표현 가능한 최댓값이다.
 
    // 범위를 초과한 값이 어떻게 표현되는가를 기억하면 된다!
    // left와 right는 이 문제에서는 매개변수로 쓰일 것이기 때문에,
    // 특이하게도 index로 쓰질 않고, 자르고자 하는 길이, cutting 함수에서의 standard로 쓰인다.
 
    unsigned long long int ans = 0;
    
    // 아래는 이분 탐색의 방식과 완전히 동일하다.
    while (left < right)
    {
        // left가 right보다 작으면 진행하되,
 
        mid = (left + right) / 2;
        // mid 값은 항상 둘의 중심으로 잡고,
 
        if (cutting(mid))
        {
            // 만약 mid 값으로 자른 결과 문제가 없다면,
            // 더 큰 값으로도 잘리는 지 알아보기 위해서 left를 mid + 1로 옮겨본다.
            ans = mid;
            left = mid + 1;
        }
        else
        {
            // mid 값으로 잘랐을 때 문제가 있다면 (개수가 부족하다면)
            // 더 작은 값으로 잘리는 지 알아보기 위해서 right를 mid로 옮겨본다.
            right = mid;
            // left를 mid + 1로 했으니 right는 mid로 옮겨도 된다.
            // 최종적으로 mid + 1 < mid == false로 while 문으로 끝날 것이다.
            // 아니면 left를 mid, right를 mid - 1로 해도 될 것이다.
        }
    }
 
    cout << ans;
    // 결과를 출력한다.
}