[백준] 14002, 14003 가장 긴 증가하는 부분 수열 4,5

수열 문제를 풀다 보니 4,5번까지 오게 됐다!

 

14002, 14003은 앞선 문제들(12015, 12738)과 다르게 부분 수열의 최대 길이뿐만 아니라 부분 수열도 출력을 해야 한다.

물론 Dp 방식으로 문제를 풀면 14002는 해결할 수 있지만 14003은 범위 때문에 시간초과로 해결하지 못한다.

 

이번 문제에서도 아래 문제에서 풀 듯이 이진탐색을 섞어서 풀었다.

[백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3

 

그래서 이진탐색을 완료하고 최대 길이는 알지만 부분 수열 요소들은 알지 못한다.

 

이때 필요한 방법이 역추적..!

이 방법을 몰라서 한참 헤매다가 다른 분들의 블로그를 참고했다.

 

역추적하는 방법은 생각보다 간단하다.

backTrace 배열에 모든 요소들의 lis에 들어가게 되는 인덱스를 담는다.

vector<int> lis;
vector<int> backTrace;
lis.push_back(array[0]);

for(int i=0;i<n;i++){
    if(lis.back() < array[i]){
        lis.push_back(array[i]);
        backTrace.push_back(lis.size() - 1);
    }
    else{
        long index = distance(lis.begin(), lower_bound(lis.begin(), lis.end(), array[i]));
        backTrace.push_back(index);
        lis[index] = array[i];
    }
}

 

그 후 backTrace를 뒤에서부터 반복하면서 lis길이와 같은 경우 배열에 담는다.

int temp = lis.size()-1;
vector<int> result;
for(int i= backTrace.size()-1; i>=0;i--){
    if(backTrace[i] == temp){
        temp--;
        result.push_back(array[i]);
    }
}

배열에 담는 부분의 경우 stack에 담았다 꺼내어 출력해도 된다.

그 후 배열을 정렬한 후 출력한다.

sort(result.begin(),result.end());

for(int i=0;i<result.size();i++)
    printf("%d ",result[i]);
printf("\n");

 

□전체 코드

void best14002(){
    int n;
    scanf("%d",&n);

    vector<int> array;
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        array.push_back(num);
    }

    vector<int> lis;
    vector<int> backTrace;
    lis.push_back(array[0]);

    for(int i=0;i<n;i++){
        if(lis.back() < array[i]){
            lis.push_back(array[i]);
            backTrace.push_back(lis.size() - 1);
        }
        else{
            long index = distance(lis.begin(), lower_bound(lis.begin(), lis.end(), array[i]));
            backTrace.push_back(index);
            lis[index] = array[i];
        }
    }

    printf("%d\n",lis.size());
    
    int temp = lis.size()-1;
    vector<int> result;
    for(int i= backTrace.size()-1; i>=0;i--){
        if(backTrace[i] == temp){
            temp--;
            result.push_back(array[i]);
        }
    }

    sort(result.begin(),result.end());
    
    for(int i=0;i<result.size();i++)
        printf("%d ",result[i]);
    printf("\n");
}

 

□ 유용한 반례

/*
 20
 322 831 212 232 545 698 260 265 324 215 701 75 156 605 851 993 425 887 691 593
 ANS: 8
 212 232 260 265 324 701 851 993
 212 232 260 265 324 701 851 887

 
 94
 43 829 750 984 32 75 09 84 327 50 984 327 50 983 47 59 341 857 034 298 76 540 23 986 578 913 570 341 29 674 31 20 874 53 890 32 768 943 76 89 03 54 702 98 75 403 27 68 95 40 24 75 80 93 47 58 90 43 276 89 024 78 95 23 47 684 53 97 04 83 92 76 34 89 02 75 809 32 76 50 94 827 65 89 020 89 76 45 309 82 76 48 09 71 2
 
 ANS:
 14
 9 23 29 31 32 54 68 75 80 89 95 97 809 827
 */