[백준/BOJ] 1654번: 랜선 자르기 ( 매개 변수 탐색 Parametric Search ) - C++ 문제 풀이

 

문제 설명

 

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

 

풀이

K개의 렌선으로부터 N개의 렌선을 만들 때, 가능한 렌선의 최대 길이를 구하는 문제입니다.

 

입력되는 값을 간단히 만들어, 어떻게 해야 원하는 값을 구할 수 있을지 생각해 보죠.

가지고 있는 렌선의 개수 K = 1이고, 렌선의 길이는 100이라고 합시다.

 

그럼, 길이 1의 렌선을 100개 만들 수 있습니다.

만약, 만들고자 하는 렌선 개수 N이 10이라면 렌선의 길이를 더 길게 할 수 있습니다.

 

그리고 스크롤바를 움직이듯이, 렌선의 길이를 계속 증가시키다 보면 만들 수 있는 최대 길이는 10이라는 것을 알 수 있습니다.

왜냐하면, 렌선의 길이가 11이 되면 만들 수 있는 렌선의 개수 N이 10이 될 수 없기 때문입니다.

 

위의 과정을 보면,

N개의 렌선을 만들 때, 가능한 렌선의 최대 길이를 구하는 문제를,

가지고 있는 렌선을 길이 x로 자르면 N개의 렌선을 만들 수 있는가 / 없는가라는 문제로 바꿔서 해결하는 것을 알 수 있습니다.

 

이런 식으로 문제를 푸는 기법을 매개 변수 탐색이라고 합니다.

 

매개 변수 탐색( Parametric Search )은 최적화 문제를 결정 문제로 바꾸어 해결하는 방식입니다.

여기서 결정 문제란 "예 / 아니요"라고 답을 할 수 있는 문제를 말합니다.

 

한 번에 와닿지는 않는데, 다른 말로 하면

최대/최소를 구하는 문제를 "예/아니요"라고 답을 할 수 있는 문제로 전환하여 해결하는 방식이라고 할 수 있습니다.

이 문제에선, 렌선을 x길이로 자르면 만들 수 있는 렌선의 개수가 N개 이상인가?라는 것이 결정 문제라고 할 수 있습니다.

 

이 결정 문제를 함수로 만들어 보자면 다음과 같습니다.

#define SIZE 10000
typedef long long MTYPE;

MTYPE L[SIZE];  // 가지고 렌선의 길이
int K; // 가지고 있는 렌선의 개수

int GetLineCount( MTYPE len){

    int cnt = 0;
    for( int i = 0; i < K; i++){
        cnt += L[i] / len;
    }

    return cnt;
}

위 함수는 렌선의 길이를 입력받아, 새로 만들 수 있는 렌선의 개수를 구하는 함수입니다.

이 함수의 결과를 N과 비교하면 결정 문제를 바로 만들 수 있습니다.

 

이 함수에 가능한 길이 값들을 입력하면,  N보다 크거나 같은 수의 렌선을 만들 수 있는 길이 구간과, 만들 수 없는 구간으로 나눌 수 있고, 그 경계에 최대 렌선 길이 값이 있습니다.

 

과정을 하나하나 분해해서 들여다보면 이렇게 될 것입니다.

 

먼저, 가능한 렌선 길이 구간은 1부터, 가지고 있는 렌선 길이의 최대 값입니다.
문제에서, 렌선을 붙일 수는 없기 때문에 가지고 있는 렌선 길이의 최대 값을 넘을 수 없습니다.

 

렌선의 길이의 1로 입력하면, 만들 수 있는 렌선의 수가 N 이상일 겁니다.

여기서 길이를 점점 길게 하면, 렌선의 수는 줄어들다가 딱 N이 되는 순간이 옵니다.

그리고, 그 길이보다 길게 만들고자 하면, N개의 렌선을 만들 수 없게 됩니다.

이렇게 해서, 렌선의 최대 값을 구할 수 있습니다.

 

하지만, 입력하는 렌선의 길이를 1부터 시작해서 순차적으로 검사한다면 수행 시간이 너무 길게 될 것입니다.

그래서, 매개 변수 탐색법은 가능한 구간을 검사하는 방법으로 이진 탐색( Binary Search ) 방식을 적용합니다.

 

이진 탐색 방식은 여기에서 볼 수 있습니다.

[백준/BOJ] 1920번: 수 찾기 ( 이진 탐색 Binary Search ) - C++ 문제 풀이

 

이러한 매개 변수 탐색을 코드로 작성하면 다음과 같습니다.

// N: 만들고자 하는 렌선의 개수
void Param_Search(int N, MTYPE s, MTYPE e){

    while( s <= e){
    
        MTYPE half = (s+e) / 2;	// 구간을 반 씩 나눈다.

        int cnt = GetLineCount( half );	// 매개 변수 탐색 함수
        
        if ( cnt >= N){		// N개 이상의 렌선을 만들 수 있는 구간에 진입
            
            maxL = half;	// 구간에서 최대 값을 저장해 둔다

            s = half + 1;	// N개를 만드는 데 실패하는 구간을 탐색한다.
        }
        else{
            e = half -1;	// 반대쪽에서 탐색
        }
    }
}

이진 탐색에 친숙하지 않다면, 설명을 보시길 권하겠습니다.

이해에 정말 도움이 됩니다.

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE 10000
typedef long long MTYPE;

MTYPE L[SIZE];  // 가지고 렌선의 길이
int K, N;   

MTYPE maxL = 0; 

int GetLineCount( MTYPE len){

    int cnt = 0;
    for( int i = 0; i < K; i++){
        cnt += L[i] / len;
    }

    return cnt;
}

void Param_Search(int N, MTYPE s, MTYPE e){

    while( s <= e){
    
        MTYPE half = (s+e) / 2;

        int cnt = GetLineCount( half );
        if ( cnt >= N){
            maxL = half;

            s = half + 1;
        }
        else{
            e = half -1;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> K >> N;

    MTYPE max_len = 0;
    for(int i = 0; i < K; i++){
        cin >> L[i];
        max_len = max(max_len, L[i]);   // 가지고 있는 최대 렌선 길이
    }

    Param_Search(N, 1, max_len);

    cout << maxL;

    return 0;
}