[백준 1654] 랜선 자르기 - JAVA

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

 

이분 탐색 문제다.

난이도는 낮은데 정답률이 처참하다.

이유는 함정? 디테일?이 있기 때문이다.

 

1. low = 0 일 때, midVal을 구하는 과정에서 divide by zero 발생

(이분 탐색에서는 low까지는 탐색하므로, 1로 놓아도 된다.)

2. mid가 int형일 때, mid = (high+low)가 int 범위 초과

 

시간 초과가 발생한다면 2번 요인으로, 오버플로 발생 및 high, low가 꼬여 의미없는 탐색을 계속 하는 경우이다.

애꿏은 가지치기만 계속했다. 안해도 통과하며, K <=10000이므로 실행 속도에서도 차이가 없다.

 

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


public class Main {

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

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

    long[] a = new long[K];
    for (int i = 0; i < K; i++) {
      a[i] = Long.parseLong(br.readLine());
    }
    Arrays.sort(a);

    long high = Integer.MAX_VALUE;
    // 0나눔 에러 뜸
    long low = 1;
    long ans = 0;

    while (low <= high) {

      // 랜선 길이
      long mid = (low + high) >>> 1;
      // 랜선 개수
      long midVal = 0;

      // 가지치기 - 최적해가 아니면 탐색 필요 x
      if (mid < ans) {
        low = mid + 1;
        continue;
      }

      for (int i = 0; i < K; i++) {
        midVal += a[i] / mid;

        // 가지치기 - N개 넘었으면 더 구할 필요 x
        if (midVal >= N) {
          break;
        }
      }

      if (midVal >= N) {
        ans = Math.max(mid, ans);

        // 랜선을 더 길게 잘라봐야 함
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    System.out.println(ans);
  }
}