BOJ 13711번 LCS 4

BOJ : https://www.acmicpc.net/problem/13711

github : https://github.com/junho0956/Algorithm/blob/master/13711/13711/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 LCS와 똑같이 풀면된다고 생각했는데

길이가 10만이여서 메모리초과가 발생할 것 같아 생각을 바꾸었습니다.

어차피 DP 배열은 굳이 N^2 가 아닌 2*N 만 있어도 가능하니, 2*N 으로 작성하였습니다.

그런데 10만이면 2*N 로 만들어봤자 시간초과가 발생할 것 같았습니다.

 

문제를 다시보니 1~N 의 모든수가 주어진다는 힌트가 있었습니다.

2개의 스트링을 비교할때는 스트링이 포함하는 모든 문자가 같다는 보장이 없지만

이 문제는 문자 즉, 모든 숫자를 서로 포함하고 있다는 조건이 있습니다.

 

이의 경우 임의의 배열이 가지는 숫자가 다른 배열에서는 몆번째 순서를 가지는지 알 수 있다면,

LCS가 아닌 가장 긴 증가하는 부분수열인 LIS 를 통해서 해답을 구할 수 있습니다.

 

ex)

A: 4 3 1 5 2

B: 5 2 1 4 3 일때

A 배열의 숫자가 B에서는 몆번째로 등장하는지 파악한다면

C: 4 5 3 1 2 가 되고, lis 길이는 2, lis를 구현하는 집합은 4,3 이 되는 것을 알 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<int> dp;
int aarr[100001];
int barr[100001];
int carr[100001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N; cin >> N;
    for (int i = 1; i <= N; i++) {
        int n; cin >> n;
        aarr[n] = i;
    }
    for (int i = 0; i < N; i++) {
        cin >> barr[i];
        carr[i] = aarr[barr[i]];
    }
 
    dp.push_back(carr[0]);
    int lis = 0;
    for (int i = 1; i < N; i++) {
        if (carr[i] > dp[lis]) {
            dp.push_back(carr[i]), lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), carr[i]) - dp.begin();
            dp[lo] = carr[i];
        }
    }
 
    cout << lis + 1;
 
    return 0;
}