문제

문제 링크

어떻게 접근할 것인가

  • 이것은 랜선 개수를 N개까지 나눠주는 최댓값을 찾아주는 문제이다.
  • 즉, 랜선 개수가 N개인 upper_bound를 찾아주면 된다!

주의할 점

  • type은 long long을 사용하자!

코드

#include <cstdio>
long long n, m, l = 1, r, mid, cnt, ans, arr[10001];

int main(){
    scanf("%lld %lld", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%lld", &arr[i]);
        if(arr[i] > r) r = arr[i];
    }
    while(l <= r){
        mid = (l + r) / 2;
        cnt = 0;
        for(int i = 0; i < n; i++)cnt += arr[i] / mid;
        if(cnt >= m){
            ans = ans < mid ? mid : ans;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    printf("%lld", ans);
}

느낀점

  • 와우… 진짜 이제 이분탐색을 잡아가는 것 같아 매우 만족스럽다…!!ㅎㅎㅎ