백준[1654] - 랜선 자르기

문제

백준 1654 문제 보기

접근 방법

랜선의 길이를 계속 바꿔가면서 필요한 랜선의 갯수와 비교해 줄이거나 늘리거나 한다. 현재 길이가 x일때 얻을수 있는 랜선이 y이고 이게 내가 필요한 랜선의 갯수보다 작다면 x의 길이를 줄이고 크거나 같다면 x의 길이를 늘리는 방식이다.

코드

#include <iostream>

using namespace std;

int K, N;
int lan[10000];

int main() {

    cin >> K >> N;

    long long start = 1;
    long long end = 0;
    for(int i = 0; i < K; i ++) {
        cin >> lan[i];
        if(end < lan[i])
            end = lan[i];
    }

    long long ans = 0;
    long long mid;
    while(start <= end) {
        int temp = 0;
        mid = (start + end)/2;
        for(int i = 0; i < K; i ++) {
            temp += lan[i] / mid;
        }

        if(temp >= N) {
            start = mid + 1;
            if(mid > ans) {
                ans = mid;
            }
        } else {
            end = mid - 1;
        }
    }
    cout << ans;
    return 0;
}