[알고리즘] 백준 1654 - 랜선 자르기

문제본문

들어가기 전

parametric search는 이진색의 원리를 이용해서 최적의 해를 구하는 방법입니다. 공부하기 위해 참고한 사이트에서는 이렇게 설명하기도 합니다.

최적화 문제를 결정 문제로 바꾸어 푸는 것이다.

정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것입니다.

O(logN + a)의 시간 복잡도를 가진 parametric search 알고리즘은 이진색과 마찬가지로 정렬된 연속적인 값들에 대해서 탐색의 범위를 1/2 씩 줄여나가며 최적의 답을 찾는 알고리즘입니다. 알고리즘의 개념이 궁금하다면 참고 링크에 더 자세히 나와있습니다.

 

문제 해석

탐색 범위 설정

long start;
long end;
long middle = (start + end) / 2

익숙한 네이밍의 변수들입니다. 이진 탐색에서 탐색의 범위를 결정짓는 변수들이었습니다. parametric search에서도 동일하게 탐색의 범위를 설정합니다.

• 오영식이 만들고자 하는 랜선의 개수는 1이상 1,000,000이하의 정수
• 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정

우선 초기 end의 값은 위 조건에 의해 오영식이 가지고 있는 랜선 중 제일 긴 랜선 길이가 됩니다

start 값은 어떨까요? 랜선이라는 물체적 특성 상 음수의 길이를 가질 수 없습니다. 또 만들고자 하는 랜선의 개수가 1개 이상이니 0 이 될수도 없죠. 따라서 초기 start 값은 1이 됩니다.

탐색

앞에서 설정한 탐색 범위에 의해서, 예시의 탐색 범위는 start = 1, end = 802가 됩니다. 앞으로 탐색은 최소와 최대의 중앙값을 가지고 비교를 시작합니다. 최소와 최대는 중앙값의 비교 결과에 따라 변경이 됩니다.
현재 중앙 값은 401입니다. K개의 랜선에서 401cm의 랜선을 만들어 봅시다.

 

802 - 2개
743 - 1개
457 - 1개
539 - 1개

401cm의 길이인 랜선은 5개만 생성할 수 있습니다. 오영식은 11개 이상의 랜선을 만들고 싶어야 하기 때문에 401cm는 적절하지 않습니다. 이제 탐색의 범위를 재설정해야 합니다. 401cm로 설정했을 때 모자랐기 때문에 401cm 이상으로 설정하면 절때로 11개를 생성할 수 없습니다. 따라서 end의 값을 401 - 1 즉, 400으로 변경합니다.

이제 탐색의 범위는 start = 1, end = 400이 됩니다. 그리고 중앙값은 200이 됩니다. 200cm로 랜선을 만들어 봅시다.

 

802 - 4개
743 - 3개
457 - 2개
539 - 2개

 

200cm의 길이인 랜선은 11개를 생성할 수 있습니다. 오영식이 원하는 랜선의 갯수와 동일합니다. 하지만 여기서 탐색을 종료하면 안됩니다. 문제에서는 N개 이상의 랜선을 생성하는 경우도 적합하다 하였고, 최대 랜선의 길이를 구하는 것이 목표입니다.

랜선을 11개 이상 생성하는 경우는 200cm뿐만이 아닐 수 있으며, 최대 랜선의 길이를 구하는 것이기에 200cm 아래로는 탐색할 필요가 없습니다. 따라서 start의 값을 200 + 1 즉, 201로 변경하여 탐색을 다시 시작합니다.

결과적으로 이진 탐색의 종료 조건과 같이 start가 end보다 커지는 순간 parametric search은 종료 하게 됩니다.

 

전체 코드

  import java.util.Scanner;

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

        int n = scanner.nextInt();
        int k = scanner.nextInt();

        long[] len = new long[n];

        long max = 0;
        for (int i = 0; i < n; i++) {
            len[i] = scanner.nextLong();
            if (max < len[i]) {
                max = len[i];
            }
        }

        long start = 1;
        long end = max;

        long middle = (1 + max) / 2;

        long answer = 0;
        while(start <= end) {

            int count = 0;
            for (int i = 0; i < n; i++) {
                count += len[i] / middle;
            }

            if (count >= k) {
                answer = Math.max(middle, answer);
                start = middle + 1;

            } else {
                end = middle - 1;
            }
            middle = (start + end) / 2;
        }

        System.out.println(answer);
    }
}

 

참고

• parametric search