1654 랜선 자르기

문제 링크

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

풀이

전형적인 이분 탐색 문제이다.
left를 0으로, right를 가장 긴 랜선의 길이로 놓고 이분 탐색을 시작한다.
만약 이미 가지고 있는 랜선들을 mid로 나눈 몫을 합한 결과가 필요한 랜선의 개수보다 많거나 같다면 랜선의 길이를 좀 더 늘려도 된다는 뜻이므로 left = mid+1로 하여 다시 이분 탐색을 시작한다.
이 때, 구하고자 하는 결과값인 result도 업데이트 한다.
만약 이미 가지고 있는 랜선들을 mid로 나눈 몫을 합한 결과가 필요한 랜선의 수보다 작다면 자르는 랜선의 길이를 줄여서 좀 더 많은 랜선을 만들 수 있도록 해야한다는 뜻이므로 right를 mid-1로 하여 다시 이분 탐색을 시작한다.

이와 같은 방법으로 이분 탐색을 반복하여 결과값을 얻을 수 있다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int K, N;
    long long left = 1, right = 0, mid;
    long long result = 0;
    int cnt;
    long long lans[10000];
    
    cin>>K>>N;
    
    for(int i=0; i<K; i++){
        cin>>lans[i];
        right = max(right, lans[i]);
    }
    
    while(left <= right){
        cnt = 0;
        mid = (left+right)/2;
        
        for(int i=0; i<K; i++){
            cnt += lans[i]/mid;
        }
        
        if(cnt >= N) {
            if(result < mid)
                result = mid;
            left = mid+1;
        }
        else
            right = mid-1;
    }
    
    cout<<result;
    
    return 0;
}