[1654] 랜선 자르기

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

1654번: 랜선 자르기

 

문제 해결 방법

이분 탐색으로 구현했습니다.

 

놓쳤던 부분

1. 랜선의 길이는 2³¹-1보다 작거나 같은 자연수이다.

int 범위를 벗어날 수 있기 때문에 long을 써줘야 합니다. 또 초기 min 값을 0이 아닌 1로 주어야 합니다.

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        long N = sc.nextInt();
        long[] lan = new long[K];
        long max = -1;

        for (int i = 0; i < K; i++) {
            lan[i] = sc.nextInt();
            max = Math.max(max, lan[i]);
        }

        long min = 1;

        while (min <= max) {
            long length = (max + min) / 2;
            int cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += lan[i] / length;
            }
            if (cnt >= N) min = length + 1;
            else max = length - 1;
        }

        System.out.println(max);
    }
}