백준 1654 랜선 자르기 - 이분탐색

코테에서 자주 나오는 유형의 이분탐색이다.

이분탐색은 정렬된 배열에서 특정 값을 찾는 일이고 후보를 한번 탐색할때마다 1/2로 줄여가는 알고리즘이다.

유튜브 영상

해당 영상을 보고 쉽게 이해할 수 있다.

1654 문제는 이분탐색을 사용하여 특정값이 아닌 범위중 최댓값, 최솟값을 찾는 유형이다.

핵심

이분탐색을 그대로 이용하면서 ans 값을 추가하여 범위에 포함될때마다 ans값을 최신화 해주면된다.

놓친점 1

반복문의 조건을 s < e 인 경우

1 1
100

의 반례가 존재한다. 즉, 처음부터 e인 지점이 정답일 경우 s가 e에 도달하기 전에 반복문이 끝난다. (실제 디버깅을 통해 확인해보면 이해하기 쉽다)

따라서 s <= e를 통해 s가 e가 될때까지 루프를 진행해야한다.

코드

        while (s <= e){
            long mid =(s+e)/2;

            // now 에 대해 계산
            int result = 0;
            for (long lan : lanLine){
                result += (lan/mid);
            }

            // 길이가 너무 짧음
            if (result >= n){
                ans = mid;
                s = mid+1;
            }
            // 길이가 너무 김
            else{
                 e = mid-1;
            }
        }