백준 1654 랜선 자르기 (성공)

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

1654번: 랜선 자르기

parametric 탐색의 대표적인 문제 중 하나

이분 탐색의 방법을 이용한다.

#include<iostream>
#include <algorithm>
 
using namespace std;
 
 
int main() {
    int K;
    cin >> K;
    int N;
    cin >> N;
 
    long long* list = new long long [K];
    for (int i = 0; i < K; i++)
    {
        scanf("%lld", &list[i]);
    }
 
    sort(list, list + K);
 
    long long start = 1;
    long long end = list[K-1];
    long long answer = 0;
    while (start <= end)
    {
        long long mid = (start + end) / 2;
        long long sum = 0;
        for (int i = 0; i < K; i++)
        {
            sum += list[i] / mid;
        }
 
        
        if (sum >= N)
        {
            start = mid + 1;
            if (mid > answer)
            {
                answer = mid;
            }
        }
        else
        {
            end = mid - 1;
        }
 
    }
    cout << answer;
 
    return 0;
}