백준 1654 (랜선 자르기) / C++

문제링크 : 1654번: 랜선 자르기 (acmicpc.net)

1654번: 랜선 자르기

> 풀이

 

간단한 이분탐색 문제입니다

#include <bits/stdc++.h>
using namespace std;

long long K, N;
long long arr[10000];

long long bSearch(long long end) {
        long long start = 0;
        long long sum = 0;
        long long len = (start + end) / 2;

        while (start <= end) {
                sum = 0;
                len = (start + end) / 2;
                if (len == 0) 
                        break;

                for (int i = 0; i < K; i++) {
                        sum += arr[i] / len;
                }

                if (sum < N) {
                        end = len - 1;
                }
                else {
                        start = len + 1;
                }
        }
        return end;
}

int main(void) 
{
        scanf("%lld %lld", &K, &N);
        for (int i = 0; i < K; i++)
                scanf("%lld", &arr[i]);
        
        sort(arr, arr + K);
        printf("%lld", bSearch(arr[K - 1]));
        return 0;
}