[백준] 1654번 : 랜선 자르기

1654번: 랜선 자르기

---

[이분 탐색]

이분 탐색 문제를 풀며 느끼는 거지만, int 보다는 long을 쓰는게 비교적 안전할 것 같다. 세심히 주의를 기울인다면 int를 사용했을 때 overflow가 나오는 것을 캐치할 수 있으나, 작은 수들을 다루다 보면 이를 무심코 지나칠 수 있는 것 같다.

 

이 문제의 핵심은

(1) left = 1, right = 갖고있는 랜선의 최대 길이

(2) int는 overflow가 발생하므로 long을 사용

(3) N개의 랜선을 잘라 cnt개로 만들었을 때, K개 보다 작으면 right = mid + 1

(이 부분을 이해하기가 조금 힘들었다. 보통 구한 값이 목표 값보다 작으면 left를 움직인다고 생각했는데, 이 문제의 경우 나누는 수가 작아질 수록 cnt가 증가하는 구조임을 명심한다.)

(4) cnt == k가 종결 조건이 아니다. (cnt > k 여도 무관)

# Code </>

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

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 n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long[] lan = new long[n];

        for(int i=0; i<n; i++)
            lan[i] = Long.parseLong(br.readLine());

        Arrays.sort(lan);

        long left = 1L, right = lan[n-1]; //left = 0을 주면 오답
        long cnt, max = 0L;

        while(left <= right){
            long mid = (left + right) / 2L;

            cnt = 0L;

            for(int i=0; i<n; i++)
                cnt += (lan[i] / mid);

            if(cnt >= k) {
                if(max < mid)
                    max = mid;

                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        System.out.println(max);
    }
}