[백준] #1654. 랜선 자르기 (실버 2)

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

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));
       StringTokenizer st = new StringTokenizer(br.readLine());

       int k = Integer.parseInt(st.nextToken());
       int n = Integer.parseInt(st.nextToken());
       int[] size = new int[k];

       int max = 0;
       for (int i = 0; i < k; i++) {
          size[i] = Integer.parseInt(br.readLine());
          if (size[i] > max) {
             max = size[i];
          }
       }


       long low = 1;
       long high = max;
       long maxLength = 0;

       while (low <= high) {
          long mid = (low+high) / 2;
          long num = 0;
          for (int s : size) {
             num += s/mid;
          }


          if (num >= n) {
             maxLength = mid;
             low = mid + 1;
          }  else {
             high = mid - 1;
          }
       }
       System.out.println(maxLength);

    }
}

 

주의할 점

1. 랜선의 최소길이는 1이므로 low의 초기값을 0이 아닌 1로 설정해야함
    (low를 0으로 설정 시 mid값 또한 0이 될 가능성이 있는데 s/mid에서 mid가 나누는 수이기 때문에 0이 되어서는 안됨!)

2. 랜선의 개수를 저장하는 num은 int의 범위를 넘길 수 있으므로 long!

3. 랜선의 길이는 2^31-1보다 작거나 같은 자연수라고 하였는데 int의 범위는 -2^31부터 2^31 - 1 → 랜선의 길이는 int범위 내에 있음

만약 int low = 1; int high = max; int mid = (low+high)/2;라면
low+high값이 2^31-1보다 작거나 같은 자연수 둘을 더한 것이기 때문에 여기서 int의 범위를 넘어서서 오버플로우가 발생할 수 있음
따라서 mid의 자료형은 long이 되어야함 (그에 따라 low, high, maxLength 또한 long!)