[백준/Java] 1654 - 랜선 자르기

https://www.acmicpc.net/problem/1654

문제

---

풀이

순차적으로 탐색하면 시간 초과가 발생한다. 이분 탐색으로 해결해야 한다

랜선의 최대 길이를 탐색 대상으로 설정하고 탐색 범위를 절반씩 줄여나가며 답을 찾아야 한다

1. 탐색 범위 설정: 최소 1cm 부터 가장 긴 랜선의 길이까지
2. 중간값(mid) 설정: 탐색 범위의 중간 길이로 모든 랜선을 잘라봄
3. 개수 확인, 범위 조절:
   • 잘라서 나온 랜선 개수가 N보다 적다면 너무 길게 자른 것이므로 탐색 범위의 상한(max)을 줄인다
   • 잘라서 나온 랜선 개수가 N보다 많거나 같다면, 가능한 길이지만 더 길게 자를 수도 있으므로 하한(min)을 높인다
4. min과 max가 교차할 때까지 반복

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] lan = new int[K];
        long max = 0;
        for (int i = 0; i < K; i++) {
            lan[i] = Integer.parseInt(br.readLine());
            // 입력한 길이 중 최댓값을 찾는다
            if (max < lan[i]) {
                max = lan[i];
            }
        }
        
        max++;

        long min = 0;
        long mid = 0;

        while (min < max) {

            mid = (min + max) / 2; // 현재 시도하는 랜선의 길이

            long count = 0;
            for (int i = 0; i < lan.length; i++) {
                // 각 랜선을 mid 길이로 잘라 총 몇개가 나오는지 계산
                count += lan[i] / mid;
            }

            /**
             * count < N -> 랜선을 너무 길게 잘랐다
             * 더 짧게 잘라야 개수가 늘어나므로, 최대 길이를 줄인다
             */
            if (count < N) {
                max = mid;
            }
            /**
             * count >= N -> 랜선을 너무 짧게 잘랐거나 딱 맞다
             * 더 길게 잘라도 될 수 있으므로, 최소 길이를 늘린다
             */
            else {
                min = mid + 1;
            }
        }

        // Upper Bound 방식으로 찾았으므로 min - 1
        System.out.println(min - 1);

        br.close();
    }
}

결과