백준 13711 - LCS 4(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13711

 

두개의 수열이 주어졌을 때, LCS를 구하는 문제입니다.

 

 

두개의 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구하는 문제입니다.

N의 값이 10^5이기에 반복문을 통해서 전부  확인해본다면 시간 초과가 생깁니다.

 

문제를 봤을 때, 각 수열은 1부터 N까지 숫자가 1개씩만으로 주어진다는 것을 알 수 있습니다.

그렇다면, 하나의 문자열을 기준으로 잡고, 다른 문자열의 숫자가 몇번 째로 나오는지를 저장만 해준다면,

이는 가장 긴 증가하는 부분 수열의 문제로 바뀐다는 것을 알 수 있습니다.

 

예를 들어보겠습니다.

문자열 1 : 1 2 4 7 8 9 6 3 5

문자열 2 : 2 4 6 8 1 3 5 7 9

-> 해당 수열의 LCS는 2 4 6 8 9로 5입니다.

 

문자열 2를 기준으로 1이 몇번째로 나왔는지를 바꾼다면

 

문자열 2 -> 2 3 7 5 1 8 9 4 6

해당 수열의 가장 긴 증가하는 부분 수열은 -> 2 3 7 8 9로 5개입니다. 따라서 5가 답임을 알 수 있습니다.

 

N 값이 크기에 lower_bound를 이용해서 수열을 구해야 시간 초과를 피할 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

int N;
int arr[100001];
int Index[100001];
vector<int> ans;

void Lower_bound(int x) {
	int st = 0;
	int fin = ans.size() - 1;
	int loc = INT_MAX;
	while (st <= fin) {
		int mid = (st + fin) / 2;
		if (ans[mid] >= x) {
			if (loc > mid) loc = mid;
			fin = mid - 1;
		}
		else {
			st = mid + 1;
		}
	}
	ans[loc] = x;
}

void solve() {
	//for (int i = 1; i <= N; i++) cout << Index[i] << " ";
	ans.push_back(Index[0]);
	for (int i = 1; i < N; i++) {
		if (ans.back() < Index[i]) {
			ans.push_back(Index[i]);
		}
		else {
			Lower_bound(Index[i]);
		}
	}
	cout << ans.size();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		arr[x] = i;
	}
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		Index[i] = arr[x];
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.