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

 

1654번: 랜선 자르기

 

 

이전에 해결한 숫자 카드 2 논리를 적용할 수 있는 문제이다.

10816번: 숫자 카드 2

 

문제를 풀기에 앞서 Parametric Search에 대한 개념을 간략하게 이해하고 넘어가보자.

 

구글에 Parametric Search에 대해 검색해보면 대부분의 블로그에서 '최적화 문제를 결정 문제로 바꾸어 푸는 것'이라고 정의한다. 

알고리즘에서 최적화 문제가 의미하는 것은 정답이 될 수 있는 후보 중에 가장 좋은 (최대 또는 최소) 정답을 찾는 문제를 말한다. 

결정 문제란 숫자 카드 2 문제에서 설명한 바와 같이 어떤 문제를 해결하는데 있어 일련의 YES or NO 판단이 연속되는 것을 말한다. 

 

즉, Parametric Search의 정의인 최적화 문제를 결정 문제로 바꾸어 푼다는 의미는, 특정 범위에서 조건에 만족하는 값 들 중 최대값 또는 최소값을 찾기 위해서 결정 문제 풀이법(여기서 사용하는 알고리즘은 이분탐색)을 사용하는 것을 말한다고 결론 내렸다.

Parametric Search의 또 다른 특징은 보통 이 방법이 사용되는 범위가 좌표나 길이와 같은 연속된 범위라는 것이다.

 

 

 

이제 문제 조건을 살펴보자.

 

현재 영식이가 자체적으로 가지고 있는 K개의 랜선을 길이가 모두 X로 같은 N개의 랜선으로 만들고자 할 때, X의 최대 길이를 구하는 프로그램을 작성해야한다. 

이 문제에서 구하고자 하는 것은 단위 랜선의 최대길이라는 것에 주목해보면 문제 해결의 실마리를 찾을 수 있다. 문제의 조건에서 단위 랜선의 길이는 항상 센티미터 단위의 정수길이로 자른다고 하였다. 따라서 단위 랜선의 길이가 될 수 있는 범위는

0 < X <= 영식이가 처음에 갖고 있는 랜선의 최대 길이

에 속하는 정수가 된다. 

 

X의 최대값이 초기 가지고 있는 랜선의 최소길이가 아닌 최대 길이인 이유는 처음 갖고 있는 랜선이 1, 100 이고 4개의 랜선이 필요한 경우에는 X의 최댓값은 25가 되기 때문이다. 따라서 초기에 갖고있는 랜선의 최대길이를 사용해야 한다.

 

추가로 이분 탐색으로 단위 랜선의 최대 길이를 구할 때에, 숫자 카드 2 문제에서의 upperBound와 같은 논리를 사용할 수 있다. 즉, 단위 랜선길이로 갖고 있는 모든 랜선을 잘랐을 때의 랜선의 총 갯수가 필요한 랜선의 개수 N 보다 '최초로 커지는 길이'를 먼저 구하고 길이 1만큼 빼주면 단위 랜선의 최대 길이를 구할 수 있다.

따라서 max++를 해준다. 

 

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int K, A[];
    static long max;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        A = new int[K];
        
        for (int i=0; i<K; i++) {
            A[i] = Integer.parseInt(br.readLine());
            // 탐색 범위의 최대길이는 초기에 갖고 있는 랜선의 최대길이 + 1
            max = Math.max(max, A[i]);
        }
        
        max++;
        
        System.out.println(upperBound(N));
        
        br.close();
    }
    
    // 필요한 랜선 갯수보다 처음 많아질 때의 단위 랜선 길이 - 1 을 반환한다.
    static long upperBound (int key) {
        
        long left = 0;
        long right = max;
        
        while (left < right) {
            
            long mid = (left + right) / 2;
            
            if (getCount(mid) >= key) left = mid + 1;
            else right = mid;
        }
        
        // 탐색이 종료된 시점의 left는 단위 랜선 길이 최댓값 + 1 상태이므로 1을 빼준다.
        return left - 1;
    }
    
    // 단위 길이로 잘랐을 때 동일한 길이의 랜선 총 갯수
    static long getCount (long unit) {
        
        long sum = 0;
        
        for (int i=0; i<K; i++) {
            sum += A[i] / unit;
        }
        
        return sum;
    }
}