백준13711 LCS4

작성일 | In

문제 링크

  • http://icpc.me/13711

사용 알고리즘

  • LIS

풀이

DP로 LCS를 구할 때 걸리는 시간은 O(N2)입니다. 하지만 N이 최대 10만이므로 다른 방법을 생각해야 합니다.
문제를 읽어보면 1부터 N까지의 정수가 한 번씩 등장한다고 합니다.

수열 B의 원소를 앞에서부터 1, 2, … , N으로 재배치하고, A번도 잘 처리를 해준다면 LIS를 구하는 문제로 바꿀 수 있습니다.
LIS는 O(N log N)만에 구할 수 있으니 시간 내에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a[101010], b[101010];
int order[101010];
int n;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int j = 1; j <= n; j++) cin >> b[j];
	for (int j = 1; j <= n; j++){
		order[b[j]] = j;
	}
	for (int i = 1; i <= n; i++){
		a[i] = order[a[i]];
	}

	int ans = 0;
	vector<int> v; v.push_back(-1);
	for (int i = 1; i <= n; i++){
		if (v.back() < a[i]){
			v.push_back(a[i]); ans++;
		}
		else{
			auto it = lower_bound(v.begin(), v.end(), a[i]);
			*it = a[i];
		}
	}
	cout << ans;
}