Boj 13711) Lcs 4

문제

백준 13711

설명

LCS 의 탈을 쓴 LIS 문제.

수열 둘의 값은 일대일 대응이 가능하므로

• 1 ~ N 의 값을 한 수열로 문자열의 인덱스로 매핑하고
• 다른 수열로 매핑된 인덱스의 오름차순 부분 수열이 LCA 와 같은 결과가 됨.

시간 복잡도

O(\(N\log{N}\))

코드

int val2idx[100001], lis[100001], n_lis;

int main()
{
	int n, t;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		val2idx[t] = i;
	}

	for (int i = 0; i < n; i++)
	{
		cin >> t;
		int* cur = lower_bound(lis, lis + n_lis, val2idx[t]);
		*cur = val2idx[t];
		if (cur - lis == n_lis) n_lis++;
	}
	cout << n_lis;
}