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

문제 설명

 

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

 

풀이

이 문제는 주어진 나무들로부터, 나무의 길이 M을 구하기 위한 절단기 높이의 최대 값을 구하는 문제입니다.

 

절단기 높이를 높이면, 잘라낼 수 있는 나무의 길이가 줄어들 것이고, 

높이를 낮추면, 나무의 길이는 늘어날 것입니다.

 

그럼, 나무의 길이가 M 이상이 되는 절단기 높이 x에서, 절단기 높이를 높이면 

나무의 길이가 점점 줄어들다 어느 순간 M이 되는 절단기 높이 H를 찾을 수 있을 겁니다.

 

만약, 절단기 높이를 이 H보다 높이면, 나무의 길이가 M보다 줄어들기 때문에, 

이 H가 최대 값임을 알 수 있습니다.

 

따라서, 이 문제를 풀기 위해서는, "절단기 높이가 x이면, 나무의 길이가  M 이상이 될 것인가"를 알아내면 됩니다.

그리고, 가능한 절단기 높이값들을 위의 질문에 던져서 "예/아니요"의 결과를 얻어내면 최대 값을 구할 수 있습니다.

 

이런 식으로, 절단기 높이의 최대 값을 구하는 문제를, 절단기 높이가 x이면 나무의 길이 M을 구할 수 있는가?라는 문제로 전환해서 문제를 푸는 방식을 매개 변수 탐색이라고 합니다.

 

매개 변수 탐색( Parametric Search )은 최적화 문제를 결정 문제로 바꾸어 해결하는 방식입니다.
여기서 결정 문제란 "예 / 아니요"라고 답을 할 수 있는 문제를 말합니다.

 

한 번에 와닿지는 않는데, 다른 말로 하면
최대/최소를 구하는 문제를 "예/아니요"라고 답을 할 수 있는 문제로 전환하여 해결하는 방식이라고 할 수 있습니다.

 

이 문제에선, 절단기 높이가 x이면 나무의 길이 M을 구할 수 있는가?라는 문제가 결정 문제입니다.

 

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

#define SIZE    1000000
typedef long long MTYPE;

MTYPE Tree[SIZE];	// 나무들의 높이

int N, M;	// N은 나무의 개수, M은 구하고자 하는 나무의 길이

MTYPE GetSumCutTreeHeight( int cutHeight ){

    MTYPE sum = 0;
    for(int i = 0; i < N; i++){
        
        if ( Tree[i] > cutHeight){
            sum += Tree[i] - cutHeight;
        }
    }

    return sum;
}

위 함수는 절단기 높이를 입력받아, 구할 수 있는 나무의 길이를 구하는 함수입니다.

이 함수 결과를 M과 비교하면, 결정 문제를 만들 수 있습니다.

 

위 함수에 가능한 절단기 높이 값들을 모아놓은 구간을 입력하면,

나무의 길이 M을 구할 수 있는 구간과, 구할 수 없는 구간으로 나눠지고 

그 경계에 절단기 높이의 최대 값이 있습니다.

 

가능한 절단기의 높이 구간은 1부터 나무의 최대 높이가 됩니다.

 

 MTYPE max_height = 0;
 
 for(int i = 0; i < N; i++){	// N: 주어진 나무들의 개수
     cin >> Tree[i];
     max_height = max(max_height, Tree[i]);   // 나무의 최대 높이
 }

 

하지만, 절단기 높이를 1부터 시작해서 순차적으로 검사한다면 수행 시간이 너무 길게 될 것입니다.
그래서, 매개 변수 탐색법은 가능한 구간을 검사하는 방법으로 이진 탐색( Binary Search ) 방식을 적용합니다.

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

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

 

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

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

    while( s <= e){
    
        MTYPE half = (s+e) / 2;		// 빠른 탐색을 위해 구간을 반 씩 나눈다.

        MTYPE sum = GetSumCutTreeHeight( half );	// 매개 변수 탐색 함수
        
        if ( sum >= M){		// 나무의 길이가 M 이상인가?
            
            maxH = half;	// 현재 최대 값을 저장

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

이진 탐색에 친숙하지 않다면, 설명을 보시길 권하겠습니다.
위의 코드가 쉽게 이해될 거라고 생각합니다.

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE    1000000

typedef long long MTYPE;

MTYPE Tree[SIZE];

int N, M;

MTYPE maxH = 0; // M 높이의 나무를 가져가기 위한 절단기의 최대 높이

MTYPE GetSumCutTreeHeight( int cutHeight ){

    MTYPE sum = 0;
    for(int i = 0; i < N; i++){
        
        if ( Tree[i] > cutHeight){
            sum += Tree[i] - cutHeight;
        }
    }

    return sum;
}

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

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

        MTYPE sum = GetSumCutTreeHeight( half );
        if ( sum >= M){
            maxH = half;

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

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M;

    MTYPE max_height = 0;
    for(int i = 0; i < N; i++){
        cin >> Tree[i];
        max_height = max(max_height, Tree[i]);   // 나무의 최대 높이
    }

    Param_Search(M, 1, max_height);

    cout << maxH;

    return 0;
}