[백준] 1654번 - 랜선 자르기 (Silver 3)

문제 링크

백준 1654번 - 랜선 자르기 (Silver 3)

문제 설명

입력받은 K개의 랜선을 먼저 입력받은 N개로 자를 때 가능한 최대 길이를 구하는 문제

주의점

랜선의 최대 길이가 $2^{31} - 1$이므로, 랜선 길이에 1만 더해도 int형으로는 overflow가 발생한다.

매개변수 탐색

조건을 만족하는 최댓값을 구하는 알고리즘으로, 이진 탐색의 응용으로 볼 수 있다.
방법은 이진 탐색과 같으나, 초기 시작 값과 끝 값을 잘 정해주어야 한다.
초기 시작 값은 항상 조건을 만족하는 경우로, 끝 값은 조건을 항상 불만족하는 경우로 정하면 된다.
최솟값을 구하는 경우라면 시작 / 끝을 반대로 잡으면 된다.

정답 코드 및 설명

import java.io.*;
import java.util.*;

public class Main {

    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());

        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        long lan[] = new long[K];
        for (int i = 0; i < K; i++) {
            lan[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(lan);

        long start = 1, end = lan[K - 1] + 1;
        while (start + 1 < end) {
            long mid = (start + end) / 2;
            if (check(mid, lan, N))
                start = mid;
            else
                end = mid;
        }
        bw.write("" + start);
        bw.close();
    }

    static boolean check(long mid, long lan[], int N) {
        int sum = 0;
        for (int i = 0; i < lan.length; i++) {
            sum += lan[i] / mid;
        }
        if (sum >= N)
            return true;
        return false;
    }

}

• 매개변수 탐색의 시간 복잡도 : $O(\log \textrm{max})$, 여기서 max는 랜선의 최대 길이
• 시작 값 1 : 랜선의 길이가 1이 되도록 자른다면, 항상 조건을 만족한다.
• 끝 값 lan[K-1] + 1 : 어떤 경우에도 랜선의 최대 길이보다 길게 자를 수는 없다.
  • overflow의 우려가 있으므로, 랜선의 길이를 long 타입으로 받는다.