[BOJ 13711] LCS 4

백준 13711번 LCS 4

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

13711번: LCS 4

---

문제

수열의 크기 N <= 100,000

두 수열이 주어질 때 LCS를 구하는 문제

 

LCS는 Longest Common Subsequence의 약자로, 최장 공통 부분 수열을 의미합니다.

두 수열이 주어질 때, 모두의 부분 수열이 되는 수열 중 가장 긴 수열의 길이를 찾으면 됩니다.

---

풀이

LCS를 구하는 문제는 DP로 풀 수 있습니다.

하지만 이는 O(N * N)의 시간 복잡도를 가집니다.

 

시간 제한이 2초인 문제에서 N이 최대 100,000 이므로 더 빠른 풀이를 찾아야 합니다.

---

다행스럽게도 각각의 수열에는 1부터 N까지 정수가 모두 한 번 씩만 등장합니다.

한 수열에 중복되는 수가 없다는 의미입니다.

 

두 가지 case에 대해서 

A와 B에 대응하는 수를 화살표로 연결해봤습니다.

 

LCS를 구하는 것과 같은 의미는 겹치지 않게 최대한 많이 화살표를 고르는 것 입니다.

 

최대한 많이 겹치지 않게 화살표를 고른 것을 빨간 색으로 표시했습니다.

 

첫 번째 케이스에서 빨간 색으로 칠한 부분 수열을 확인해보니

{1, 2, 4} 입니다.

이는 두 부분 수열 모두 들어가는 공통 수열이며, 길이가 가장 긴 부분 수열이기에 LCS가 맞습니다.

 

두 번째 케이스도 확인해보면

{1, 3, 4}가 나오고 이는 LCS가 맞습니다.

---

화살표를 겹치지 않게 고른다는 것은

임의의 수 i < j 에 대해서 arr[i] < arr[j]를 만족한다는 의미 입니다.

 

이는 LIS의 성질입니다.

즉, LIS를 구하는 문제로 바꿔 풀 수 있습니다.

https://kdr06006.tistory.com/11

LIS (Longest Increasing Sequence)

 

수열 A와 B가 주어질 때,

수열 B의 원소가 수열 A에 어디에 위치하는지로 정보를 바꿔줍니다.

그리고 수열 B의 LIS를 구해주면 정답입니다.

 

---

코드

#include <cstdio>

#define min(a, b) (a) < (b) ? (a) : (b)

const int SIZE = 1e5 + 4;

int pos[SIZE], arr[SIZE];

struct Vector {
	int arr[SIZE];
	int sz;

	void put(int idx, int n) {
		if (idx == sz) arr[sz++] = n;
		else arr[idx] = min(arr[idx], n);
	}

	int operator[](int idx) { return arr[idx]; }
};

struct LIS {
	Vector lis;

	int lower(int key) {
		int l = 0, r = lis.sz - 1;
		
		while (l <= r) {
			int m = l + r >> 1;
			if (lis[m] > key) r = m - 1;
			else l = m + 1;
		}

		return r + 1;
	}

	int solve(int N) {
		for (register int i = 0; i < N; ++i) {
			int t = lower(arr[i]);
			lis.put(t, arr[i]);
		}

		return lis.sz;
	}
}lis;

int main()
{
	//freopen("input.txt", "r", stdin);

	int N;
	scanf("%d", &N);
	
	register int i;
	int t;
	for (i = 0; i < N; ++i) {
		scanf("%d", &t);
		pos[t] = i + 1;
	}

	for (i = 0; i < N; ++i) {
		scanf("%d", &t);
		arr[i] = pos[t];
	}

	printf("%d\n", lis.solve(N));
}