알고리즘) 랜선 자르기(백준 이분탐색 1654번)

문제(백준)

 문제 자체는 어렵지 않다. 이전 글인 '나무 자르기' 글을 참고하면 쉽게 풀 수 있는 문제다. 문제의 조건 중 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이 때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오'는 중간값(mid, 자르는 길이)로 잘랐을 때의 랜선 길이의 수(cnt)가 N보다 크더라도 조건에 일치하는 것으로 본다는 의미를 가진다. 또한, 해당 조건(N개 이상의 랜선을 만들 수 있도록 랜선 길이를 정하는 방법)에 일치하는 경우의 수가 여러 가지이며, 이 경우들 중에서 자르는 랜선의 최대 길이(여기서는 이를 확인하기 위한 값으로 mid 사용)가 최댓값인 경우를 찾는 문제이다. 즉, cnt가 M과 같은 경우에는 lt를 mid + 1 로 변경시켜서 두 범위 중 더 큰 범위에서 탐색을 계속 진행해야 한다는 말이다.

작성 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private long solution(int k, int n, int[] list) {
        long answer = 0;

        long lt = 1;
        long rt = Arrays.stream(list).max().getAsInt();

        while (lt <= rt) {
            long mid = (lt + rt) / 2;
            long cnt = 0;
            for (int i = 0; i < k; i++) {
                cnt += (list[i] / mid);
            }

            if (cnt >= n) {
                lt = mid + 1;
                answer = mid;
            } else rt = mid - 1;
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);

        int k = sc.nextInt();
        int n = sc.nextInt();
        int[] list = new int[k];
        for (int i = 0; i < k; i++) list[i] = sc.nextInt();

        System.out.println(main.solution(k, n, list));
    }
}