일단 나는 이 문제를 LIS nlogn 구현 문제 밀다가 발견한거기 때문에
알고리즘 접근에 있어서의 문제는 없었다.
https://www.acmicpc.net/problem/13711
13711번: LCS 4
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3]
www.acmicpc.net
https://jason9319.tistory.com/113
[최장 증가 수열] LIS(Longest Increasing Subsequence)
이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다. LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다. 쉬운 이해를 위해서 예를 들어보겠습
jason9319.tistory.com
lis의 개념 학습은 이 블로그를 참고했다.
이 문제에서의 핵심은 숫자가 1 2 3 4 5 처럼
깔끔하게 증가하는 꼴로 나타나지 않아서 바로 LIS를 적용시킬 수가 없는데,
이 입력들을 1 2 3 4 5 로 보는게 아니라
a b c d e 쯤으로 보면 훨씬 쉽게 이해가 갈 것 이다.
b c a
a b c 에서 lcs를 구하는 과정을 위해
b=1
c=2
a=3 이라는 값을 넣어주면
1 2 3
3 1 2 로 lis로 구할 수 있는 꼴이 되는 것이다.
이렇게 나온 3 1 2 배열에 대한 lis를 진행해주면 된다.
#include <bits/stdc++.h>
#define INF 123456789
using namespace std;
vector<int> v;
vector<int> va;
int vb[123456] = {0};
int vc[123456] = {0};
int main(){
v.push_back(-INF);
int n,a,b;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d", &a);
va.push_back(a);
}
for(int i=0; i<n; i++){
scanf("%d", &b);
vb[b] = i;
}
for(int i=0; i<n; i++){ vc[i] = vb[va[i]]; }
for(int i=0; i<n; i++){
if(v[v.size()-1] < vc[i]){
v.push_back(vc[i]);
}else{
auto it = lower_bound(v.begin(), v.end(), vc[i]);
*it = vc[i];
}
}
printf("%d", v.size()-1);
return 0;
}몇문제 더 풀어보도록 하자 ^^