[알고리즘] 백준 - 랜선 자르기

백준 - 랜선 자르기

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    static int K, N;
    static long[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        K = Integer.parseInt(inputs[0]); //가지고 있는 랜선의 개수
        N = Integer.parseInt(inputs[1]); //필요한 랜선의 ㄱ새ㅜ
        arr = new long[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        long left = 0;
        long right = Arrays.stream(arr).max().getAsLong();
        long maxLength = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            if (mid == 0) {
                left += 1;
                continue;
            }
            if (getCount(mid) >= N) { //필요 개수 이상이면 더 길게 짤라도 된다.
                maxLength = Math.max(maxLength, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(maxLength);

    }

    private static int getCount(long length) {
        int count = 0;
        for (long wire : arr) {
            if (length != 0) {
                count += wire / length;
            }
        }
        return count;
    }
}

일반적인 이분 탐색 문제라고 생각했지만 몇몇 트랩이 있었다.
우선 mid를 구할 때 보통 (left + right) / 2라고 하는데 left나 right의 범위가 int 전체라면 오버플로우가 날 수 있다. 그래서 long타입으로 해주든가 left + (right - left) / 2 이런식으로 해줘야 한다.

두 번째는

1 1 
1

이런 반례였다. 기존 코드에서는 mid가 0일 때를 처리 안해줬는데 그러면 항상 else 문에 들어가게되고, 항상 right가 줄어드니 답이 안나오는 것이다.