[BOJ] 1654번 : 랜선 자르기

접근 방법

랜선의 길이는 1 이상 2^31-1 이하이므로 랜선을 자를 수 있는 길이 또한 1 이상 2^31-1 이하입니다. 최악의 경우 10,000개의 랜선을 2^31-1가지 길이로 자르는 경우를 계산하게 되므로 시간 제한을 초과하게 됩니다. 이진 탐색으로 랜선을 자를 길이를 알아내면 10,000×log 2^31-1(약 310,000)의 경우를 탐색하게 되므로 시간 제한내에 해결이 가능합니다.

코드

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

public class Main {

    static int n;
    static int k;
    static int[] cords;
    static int result;

    public static void main (String[] args) {
        input();
        func();
        System.out.println(result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        k = sc.nextInt();
        n = sc.nextInt();

        cords = new int[k];

        for (int i = 0; i < k; ++i) {
            cords[i] = sc.nextInt();
        }

        sc.close();
    }

    static void func() {
        long left = 1;
        long right = Integer.MAX_VALUE;

        // 이진 탐색으로 검색
        while (right >= left) {
            long mid = ((left + right) / 2);

            // 만들 수 있는 랜선의 수가 원하는 랜선의 수보다 더 많을 경우
            // 해당 길이보다 짧게 잘라도 원하는 랜선보다 더 많으므로
            // left를 mid + 1로 설정
            if (getNumberOfCords((int)mid) >= n) {
                result = (int)mid;
                left = mid + 1;
            } else {
                // 아닐 경우 해당 길이보다 더 짧게 잘라야 하므로
                // right를 mid - 1로 설정
                right = mid - 1;
            }
        }
    }

    // cut만큼의 길이로 자를 경우 만들 수 있는 랜선의 수를 반환하는 함수
    static int getNumberOfCords(int cut) {
        int sum = 0;

        for (int i : cords) {
            sum += i / cut;
        }

        return sum;
    }
}