BOJ01654 랜선 자르기

https://www.acmicpc.net/problem/1654 (opens new window)

박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 요청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박상원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶기 때문에 K개의 랜선을 잘라서 만들어야 한다.

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정한다. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정한다. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성한다.

매개 변수 탐색 Parametric Search

최적화 문제(특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem) 로 바꾸어 푸는 것이다.

적절한 길이를 찾을 때 까지 랜선의 길이를 조절한다. 그 뒤 문제의 조건을 만족하는지 확인한 후 탐색 범위를 좁혀서 해결한다.

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1654 {

    static int k, n;
    static int[] lengths;

    private static long binarySearch(long start, long end) {
        long result = 0;
        while (start <= end) {
            int total = 0;
            long mid = (start + end) / 2;

            for (int i = 0; i < k; i++) {
                total += (lengths[i] / mid);
            }

            if (total < n) {
                end = mid - 1;
            } else {
                result = mid;
                start = mid + 1;
            }
        }

        return result;
    }

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

        k = scanner.nextInt(); // 랜선의 개수
        n = scanner.nextInt(); // 필요한 랜선의 개수

        lengths = new int[k];
        for (int i = 0; i < k; i++) {
            lengths[i] = scanner.nextInt();
        }

        int max = Integer.MIN_VALUE;
        for (int length : lengths) {
            max = Math.max(max, length);
        }

        System.out.println(binarySearch(1, max));
    }
}

#algorithm #BOJ #이분 탐색 #매개 변수 탐색 #파라메트릭 서치