[백준 1654] 랜선 자르기(Java)

문제 링크 : https://www.acmicpc.net/problem/1654

이 문제는 이진 탐색으로 풀 수 있습니다. K가 10,000 이하, N이 1,000,000 이하이기 때문에 이중 반복문을 돌리게 될 경우 O(10^10) 으로 시간 초과가 나타납니다. 따라서 이진 탐색을 통하여 탐색 속도를 줄여야 합니다. 이진 탐색의 최댓값은 가장 큰 수로, 최솟값은 1로 설정하셔서 조건에 맞게 진행하시면 됩니다. 여기서 실수로 최솟값을 0으로 설정하시게 되면 mid가 0이 되어 0으로 나누는 런타임 에러가 발생할 수 있으니 조심하시면 됩니다.

다음은 코드입니다.

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

public class Main{
    static int K,N;
    static long max = 0, min = 1;
    // 랜선 길이가 int 범위를 초과하므로 long으로 받기
    static ArrayList<Long> req = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        // 이진 탐색 실행
        // max : 가장 큰 수
        // min : 1

        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine());
            long num = Long.parseLong(st.nextToken());
            req.add(num);
            if(max < num) max = num;
        }

        while(min <= max){
            long mid = (min+max)/2;

            long sum = 0;
            for(int i=0;i<req.size();i++){
                // 랜선을 자른 길이만큼을 더함
                sum += (req.get(i)/mid);
            }

            // 만약 자른 길이의 합이 목표값보다 작다면
            // 현재 길이가 긴 것이므로 max값을 mid-1로 줄이기
            if(sum < N) max = mid-1;
            // 만약 자른 길이의 합이 목표값보다 크다면
            // 현재 길이가 짧은 것이므로 min값을 mid+1로 늘리기
            else min = mid+1;
        }

        // mid값이 mid+1인데 구하고자 하는 길이는 mid이므로 -1해서 진행하기
        System.out.println(min-1);
    }
}