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

 일전에 풀었던 가장 긴 증가하는 부분 수열 2 문제에서 한 단계 더 나아간 문제이다. 그 때의 풀이처럼 DP와 이진탐색을 골자로 진행한다.

[백준 12015] 가장 긴 증가하는 부분 수열 2 (tistory.com)

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

 

 저 때와 비교해서 달라진 것은, 결과로 얻어지는 LIS를 출력해야 한다는 점이다. 저 포스트에서도 작성했듯이, 해당 풀이에서는 최종적으로 얻어지는 LIS의 길이만 알 수 있을 뿐 실제 LIS의 구성에 대한 정보는 소실된다. 따라서 계산 과정에서 필요한 데이터들을 저장해두고 역추적 해서 실제 LIS를 알아내야 한다.

 DP 배열을 채워나갈 때, 각 시점에 원소들은 이진 탐색을 통해 특정 길이의 LIS 끝 값으로 자리잡게 된다. 이 때, LIS 내에서 본인 앞에 위치하는 원소의 원래 배열 내 인덱스 값을 알 수 있다면, 최종적으로 LIS의 끝 값의 원래 인덱스부터 시작해서 완성된 LIS를 역추적할 수 있을 것이다.

 또 각 시점에 본인 앞에 위치하는 원소의 원래 인덱스를 알아내려면, 항상 DP 배열에 대응되는 인덱스 배열을 따로 관리해줄 필요가 있다. 결국 특정 길이 n의 LIS는 그 시점의 길이 n-1인 LIS의 뒤에 탐색 중인 원소를 붙인 꼴이 될테니까, 이를 이용하면 역추적을 위한 prev 배열을 만들 수 있게 된다.

 

 요약하자면, DP 배열을 형성하면서 대응되는 인덱스 배열을 같이 관리한다. 이를 이용해서 각 원소별로 LIS 상에서 본인 앞에 위치하는 원소의 인덱스를 담아둘 prev 배열을 함께 완성해 나간다. DP 배열을 완성했다면, 최종적으로 만들어진 인덱스 배열에서 가장 긴 LIS 배열의 끝 값 인덱스를 기점으로, prev 배열을 통해 역추적 해나가며 실제 LIS 배열을 찾아낸다. 이를 전체 길이와 함께 내용물을 출력해주면 된다. 

 

 발상 난이도 자체만 보면, 따로 공부를 하지 않았을 때를 기준으로 기존의 LIS 길이 찾는 로직 떠올리는게 더 어렵지 않나싶다. 대신에 적절하지 못한 자료구조를 도입해서 해결하려 하면 메모리 조건이 빡빡하니, 그 점을 좀 더 신경 써줬어야 하는 문제.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[1000000];

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

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

    vector<int> dp;
    vector<int> prev(n, -1);
    vector<int> lisInd;

    dp.push_back(arr[0]);
    lisInd.push_back(0);

    for(int i=1; i<n; i++) {
        if(dp[dp.size()-1]<arr[i]) {
            dp.push_back(arr[i]);
            lisInd.push_back(i);
            prev[i] = lisInd[lisInd.size()-2];
        } else {
            auto lb = lower_bound(dp.begin(), dp.end(), arr[i]);
            *lb = arr[i];
            lisInd[lb-dp.begin()] = i;
            if(lb-dp.begin()>0) {
                prev[i] = lisInd[lb-dp.begin()-1];
            }

        }
    }

    vector<int> lis;
    for(int i=lisInd[lisInd.size()-1]; i!=-1; i=prev[i]) {
        lis.push_back(arr[i]);
    }

    cout << dp.size() << '\n';
    for(int i=lis.size()-1; i>=0; i--) {
        cout << lis[i] << " ";
    }
}