[백준/BOJ] 12015번: 가장 긴 증가하는 부분 수열 2 ( 이진 탐색법 ) - C++ 문제 풀이

 

문제 설명

 

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

 

풀이

이 문제는 주어진 수열에서 오름차순의 숫자들을 찾아서 부분 수열을 만드는 문제입니다.

조건은 만들 수 있는 부분 수열 중에서 길이가 가장 긴 부분 수열을 찾아야 한다는 것입니다.

 

예를 들어, 다음과 같은 수열이 주어졌다고 해보죠.

10 20 30 15 20 25

그러면, 만들 수 있는 오름차순의 부분 수열은 2개가 있습니다.

10 20 30, 10 15 20 25

이 중에서 길이가 더 긴 10 15 20 25의 부분 수열이 정답입니다.

그래서, 길이 4를 출력하는 문제입니다.

 

이 문제를 푸는 아이디어는, 기존에 선택한 큰 숫자를 작은 숫자로 바꿔가면, 다음에 나오는 고를 수 없는 숫자도 고를 수 있게 된다는 것입니다.

 

위의 10, 20, 30, 15, 20, 25의 수열로 설명하도록 하겠습니다.

 

먼저 첫 번째 숫자 10을 뽑습니다.

그다음 20이 10보다 크므로 20을 10 뒤에 붙여 수열을 만듭니다.

그다음 30이 20보다 크므로 30을 20 뒤에 붙입니다.

 

다음에 나온 숫자 15는 30보다 작으므로, 오름차순에 어긋나기 때문에 버려야 합니다.

그러나, 15를 뽑아놓은 20과 교체합니다.

20은 15보다 크고, 15와 가장 가까운 숫자입니다.

그러면 어떻게 될까요?

 

먼저 현재 뽑은 부분 수열의 길이는 3으로 변함이 없습니다. ( 10, 15, 30 )

그리고, 그다음 나오는 20을

위와 마찬가지로, 20보다 크고, 20과 가장 가까운 30과 교체할 수 있게 됩니다.

이것은 이전에 20이 15로 교체되었기 때문에 가능합니다. ( 10, 15, 20 )

 

그러면, 30을 뽑았기 때문에 뽑을 수 없었던 25를 부분수열의 다음 숫자로 추가할 수 있게 됩니다.

그래서 10, 15, 20, 25의 더 긴 부분 수열을 찾을 수 있습니다.

 

이 과정에서 제일 중요한 일은 교체하고자 하는 x보다 "크면서 가장 가까운 숫자"를 찾는 것입니다.

이러한 숫자를 찾기 위해서, 이진 탐색을 수행합니다.

 

이진 탐색이 가물가물 하시면 여기에서 참고하실 수 있습니다.

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

 

먼저 전체적인 과정을 보겠습니다.

#define SIZE    1000000
int A[SIZE];

int main(){
    
    int N;
    cin >> N;	// 수열의 크기

    for( int  i = 0; i < N; i++){
        cin >> A[i];	// 주어진 숫자들
    }

    int cnt = 1;    // 첫 번째 멤버 입력
        
    for( int i = 1; i < N; i++){
        
        if ( A[cnt-1] < A[i]){ // 오름차순이면 부분 수열으로 뽑는다
            cnt++;
            A[cnt-1] = A[i];
        }
        else{
            
            // 작은 숫자가 나오면, 기존에 뽑은 숫자에서 크고, 가장 가까운 숫자와 교체
            ChangeToSmallMember( A[i], 0, cnt-1);
        }
    }

    cout << cnt;	// 뽑은 부분 수열의 길이를 출력

    return 0;
}

주어진 수열을 순환하면서, 부분 수열의 최대 값보다 더 큰 숫자가 나오면 부분 수열로 뽑습니다.

그리고, 작은 숫자 x가 나오면, 기존에 뽑은 숫자 중에서 x보다 크고, 가장 가까운 숫자를 찾아 x와 교체합니다.

이 과정을 통해서, 기존의 부분 수열을 더 작은 숫자들을 가진 수열로 바꿀 수 있습니다.

 

뽑은 부분 수열에서 숫자 x보다 크고, 가장 가까운 숫자를 찾는 함수는 다음과 같습니다.

이진 탐색을 기반으로 하여, 조금 수정된 버전입니다.

void ChangeToSmallMember( int New, int s, int e){

    while( s <= e){
        
        int half = ( s + e ) / 2;	// 탐색 구간을 1/2로 줄인다.

        if ( A[half] < New ){
            s = half + 1;
        }
        else if ( New < A[half] ){ 

            e = half;

            if ( s == e){	
                A[s] = New;	// New 보다 크고, 가장 가까운 숫자와 교체
                break;
            }
        }
        else{
            break;	// 같은 숫자가 이미 있으면 탐색 중단
        }
    }
}

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE    1000000
int A[SIZE];

void ChangeToSmallMember( int New, int s, int e){

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

        if ( A[half] < New ){
            s = half + 1;
        }
        else if ( New < A[half] ){ 

            e = half;

            if ( s == e){
                A[s] = New;
                break;
            }
        }
        else{
            break;
        }
    }
}

int main(){

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

    for( int  i = 0; i < N; i++){
        cin >> A[i];
    }

    int cnt = 1;    // 첫 번째 멤버 입력
        
    for( int i = 1; i < N; i++){
        if ( A[cnt-1] < A[i]){ 
            cnt++;
            A[cnt-1] = A[i];
        }
        else{
            ChangeToSmallMember( A[i], 0, cnt-1);
        }
    }

    cout << cnt;

    return 0;
}