BAEKJOON 1654 - 랜선 자르기

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

우선 만들어진 랜선의 개수가 필요한 개수보다 크거나 같은 경우 최대값을 답으로 구하기 위해 비교 부분에서 일반적인 이진탐색과 다르게 구현을 해야 됩니다. 그리고 많이 틀릴 수 있는 부분이 오버 플로인데 랜선의 길이는 2^31-1보다 작거나 같은 자연수이기 때문에 low 와 high 를 합하는 과정 등에서 오버 플로가 발생할 수 있으니 비교 관련 변수는 모두 long long 으로 선언을 해두는게 안전합니다.

#pragma warning (disable:4996)
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll getLineNumber(const int* numbers, int length, int n)
{
    ll ret = 0;
    for (int i = 0; i < n; i++)
        ret += numbers[i] / length;
    return ret;
}
 
ll binarySearch(const int* numbers, ll low, ll high, ll needNumber, ll n)
{
    ll ret = 0;
    while (low <= high)
    {
        ll mid = (low + high) / 2;
        ll lineNumber = getLineNumber(numbers, mid, n);
        if (needNumber > lineNumber)
        {
            high = mid - 1;
        }
        else
        {
            ret = max(ret, mid);
            low = mid + 1;
        }
    }
    return ret;
}
 
int main()
{
    int n, needNumber;
    ll lowest, hightest;
    lowest = hightest = 0;
    scanf("%d %d", &n, &needNumber);
    int* lengths = new int[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &lengths[i]);
        hightest = max(hightest, (ll)lengths[i]);
    }
 
    printf("%d\n", binarySearch(lengths, lowest, hightest, needNumber, n));
    delete[] lengths;
    return 0;
}