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

문제 : 1654

풀이 point

이진검색 parametic search를 활용할 수 있다. 자세한 내용은 나무 자르기를 참고.

풀이 방법

랜선을 N개 이상 확보하면서 랜선의 최대 길이를 이진검색을 통해 찾는다.

코드

//백준 1654, 랜선 자르기

#include <iostream>

long long arr[10'000];
int K, N;

bool solve(long long mid){
    int ans{0};
    for(int i{0}; i<K; ++i){
        ans += arr[i] / mid;
    }
    return ans >= N;
}

int main (){

    std::cin >> K >> N;
    for(auto i{0}; i<K; ++i){
        std::cin >> arr[i];
    }

    long long st{1}; long long end = (1LL << 31)-1;
    while(st < end){
        auto mid = (st+end+1) / 2;
        if(solve(mid)) st = mid; 
        else end = mid -1;
    }

    std::cout << st;

    return 0;
}

2025-01-29T01:27:56.670Z