백준 - 1654 랜선자르기

[문제링크]

이전에 풀었던 문제인데, 재채점으로 인해 틀렸다하여 다시 풀었던 문제이다.(자료형만 바꿔주니 다시 맞게 나왔다.)

이분법으로 푸는 문제인데 이분 탐색에서 upper bound 방식으로 풀어야 한다.

왜냐하면 필요한 랜선의 길이인 N을 만드는 경우는 엄청 다양하기 때문이다. 그 다양한 길이 중 가장 긴 랜선의 길이를 찾아야한다.

밑은 이 문제의 코드이다.

#include <cstdio>
#include <algorithm>
long long k,n,l[10010], mi=0,m; 
long long bs(long long s, long long e) {
    //이분 탐색을 시작한다.
    while (s<=e) {
        m = (s + e) / 2;
        long long v = 0;
        // 각 종류의 랜선들을 현재의 길로 나눠 갯수를 구한다. 
        for (int i = 0; i < k; i++)
            v += l[i] / m;
            
        //갯수가 '같거나' 크면 m의 값을 1 증가시켜주고 이분탐색을 진행한다. 
        if (v >= n) s = m + 1;
        else if (v < n) e = m - 1;
    }
    return e;   
}
int main() {
    scanf("%lld %lld", &k, &n);
    for (int i = 0; i<k; i++) {
        scanf("%lld", &l[i]);
        mi = std::max(mi, l[i]);
    }
    printf("%lld",(n==1)?mi:bs(1, mi));
}