[PS] 백준 1654번: 랜선 자르기

|

문제

내가 이해한 문제 내용

현재 가지고 있는 랜선의 개수 $K$와 있어야 하는 랜선의 개수 $N(K\le N)$이 주어질 때 $K$를 잘라서 $N$개 이상의 랜선을 만들 수 있는 랜선길이의 최댓값을 구하여라.

접근 방식

좀 고민하다가 이분탐색인걸 캐치해서 0부터 랜선의 최대길이를 양쪽 끝으로 두고 이분탐색을 돌렸다.

어려웠던 점 & 배운 점

이분탐색의 종료를 단순히 $K==N$ 시점에 해버려서 틀렸는데 그 이유는 $N$개 이상의 랜선이면서 길이가 더 길어질 수 있는 여지가 있기 때문이었다. 또한 길이가 1인 경우 $2/1=0$이 되버려서 $K$개의 랜선을 0으로 나누는 꼴이 되서 런타임에러가 발생했다. 이분탐색은 제출하기 전에 좀더 신경써야 할 부분이 많다는 것을 배웠다. 아 또 범위를 잘 봐야 하는데 범위가 int의 최댓값이어서 그 최댓값을 벗어날 때가 있었다.

시간복잡도

랜선길이의 최댓값을 $M$이라 하면 $O(KlgM)$

코드

#include <cstdio>

typedef long long ll;

int k,n,len;
ll lan[1000001];
ll m,max,ans;

int main(void)
{
    scanf("%d%d",&k,&n);
    for(int i=0; i<k; i++) {
        scanf("%lld",&lan[i]);
        if(max<lan[i]) max = lan[i];
    }

    ll l=0,r=max;
    while(l<=r){
        m = (l+r)/2 ? (l+r)/2 : 1;
        printf("%lld~%lld: %lld\n",l,r,m);
        len = 0;
        for(int i=0; i<k; i++)
            len += (lan[i]/m);
        if(len>=n) ans = m;
        if(len<n) r = m-1;
        else l = m+1;
    }
    printf("%lld",ans);
    return 0;
}