문제 출처

단계별로 풀어보기 > 이분 탐색 > 랜선 자르기
https://www.acmicpc.net/problem/1654

문제 설명

접근 방법

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class 랜선_자르기 {

    public static List<Long> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        long K = Long.parseLong(st.nextToken());
        long N = Long.parseLong(st.nextToken());

        long max = 0;
        for(int i = 0; i < K; i++){
            long x = Long.parseLong(br.readLine());
            list.add(x);
            if(x > max) max = x;

        }

        max++;

        long min = 1;
        long mid = 0;

        while(min < max) {

            mid = (max + min)/2;

            long count = 0;

            for(int i = 0; i < list.size(); i++){
                count += list.get(i)/mid;
            }

            if(count < N){
                max = mid;
            } else {
                min = mid + 1;
            }
        }

        bw.write(String.valueOf(min-1));
        bw.flush();
        bw.close();
        br.close();

    }

}

알게된 점

Upper Bound에 대해서 코드를 이해하는데 생각보다 오래 걸렸다.
Upper Bound는 처음으로 거짓이 되는 최소 x를 찾는 방식으로, 조건이 거짓이면 거짓 구간을 왼쪽으로 당기고, 참이면 기존 mid보다 더 큰(mid +1) 쪽을 탐색한다.
또한 마지막에 min-1의 결과를 정답인 것도, upper bound 방식을 사용하여 거짓이 되는 부분을 찾았기 때문에, 그보다 1작은 값이 정답이 된다.

해당 코드의 시간복잡도는 O(K log N)이다.

참고 링크
https://st-lab.tistory.com/269

문제푼 흔적