BOJ 13711 | LCS 4

진짜 전형적인 구현 쉽고 아이디어 어려운 문제다.

근데 사실 LCS를 특정한 조건 아래서 $O(NlogN)$으로 푸는건 너무 웰노운이라서 이게 P5를 줘도 되나 싶긴 한데
그걸 모르고 풀면 P5 이상을 줘도 될 것 같다.

사실 LCS 좀 연습하려고 LCS 번호순으로 순회하다가 이거 보자마자 LIS다 싶긴 했는데 LIS 자체가 잘 기억이 안나서 LIS 몇개 연습하고 돌아왔다.

아이디어를 알고 나면 아주 쉽다.

이 아이디어는 좌표압축이나 해쉬 알고리즘이랑도 살짝 비슷한 면이 있다.

우선, 수열 A와 B는 모두 1~N까지의 정수이고, 한 번씩만 등장하기 때문에 B의 모든 원소를 A에서 찾을 수 있다.

그러므로 B[i]는 B의 i번째 수이지만, A의 k번째 수이기도 하다.
모든 i에 대해 B[i] = k를 하게 되면, 이 문제를 LIS로 풀 수 있다.

AFGBCED

ABDC

의 LCS를 구한다고 해보자.
B[i] = k를 전부 해주고 나면,

1 4 7 5 가 된다. 여기서 LIS를 구해주면 $[1, 4, 5]$ 혹은 $[1, 4, 7]$로 길이가 3이다.
다시 알파벳으로 복원하려면 A[k]를 해주면 되므로 아주 간단하다.

왜 이런 일이 가능한가 모르겠다면, 다음을 따라가보자.
우선 A 배열에서 B에 등장하지 않는 모든 원소는 LCS를 구하는 데 필요가 없다.
그러므로 지울 수 있다.
ABCD
ABDC

따라서 A와 B의 길이는 항상 같게 만들 수 있다.
여기서 LCS를 구하기 위해 왼쪽부터 오른쪽까지 쭈욱 따라가며 탐색한다고 생각해보자.
탐색을 거듭할 때마다 index는 계속 늘어나지 않겠는가?

그러므로 LCS가 만들어지면서 index가 줄어들면 안 된다.

B[i] = k인 상태에서는 B는 A의 index로 나타내지게 되는데, 여기서 LCS는 항상 증가하는 부분 수열로 나타날 것이다.
증가하는 부분 수열 중 최장 길이를 구해야 하므로 LIS 문제와 동일한 문제가 된다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int board[501];
int dp[101];

vector<int> v1, v2;
int idx[100001];

int main(){
	int N; cin >> N;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		v1.push_back(t);
		idx[t] = i;
	}
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		v2.push_back(idx[t]);	
	}
	
	
	//LIS O(NlogN)
	vector<int> lis;
	for (auto &i: v2){
		if (lis.size() == 0 || lis.back() < i) lis.push_back(i);
		else lis[lower_bound(lis.begin(), lis.end(), i) - lis.begin()] = i;
		
		//for (auto &j: lis) debug << j << ' ';
		//debug << endl;
	}
	
	cout << lis.size();
}