BOJ : https://www.acmicpc.net/problem/13711
github : https://github.com/junho0956/Algorithm/blob/master/13711/13711/%EC%86%8C%EC%8A%A4.cpp
처음에는 LCS와 똑같이 풀면된다고 생각했는데
길이가 10만이여서 메모리초과가 발생할 것 같아 생각을 바꾸었습니다.
어차피 DP 배열은 굳이 N^2 가 아닌 2*N 만 있어도 가능하니, 2*N 으로 작성하였습니다.
그런데 10만이면 2*N 로 만들어봤자 시간초과가 발생할 것 같았습니다.
문제를 다시보니 1~N 의 모든수가 주어진다는 힌트가 있었습니다.
2개의 스트링을 비교할때는 스트링이 포함하는 모든 문자가 같다는 보장이 없지만
이 문제는 문자 즉, 모든 숫자를 서로 포함하고 있다는 조건이 있습니다.
이의 경우 임의의 배열이 가지는 숫자가 다른 배열에서는 몆번째 순서를 가지는지 알 수 있다면,
LCS가 아닌 가장 긴 증가하는 부분수열인 LIS 를 통해서 해답을 구할 수 있습니다.
ex)
A: 4 3 1 5 2
B: 5 2 1 4 3 일때
A 배열의 숫자가 B에서는 몆번째로 등장하는지 파악한다면
C: 4 5 3 1 2 가 되고, lis 길이는 2, lis를 구현하는 집합은 4,3 이 되는 것을 알 수 있습니다.
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
35
36
37
38
39
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> dp;
int aarr[100001];
int barr[100001];
int carr[100001];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N; cin >> N;
for (int i = 1; i <= N; i++) {
int n; cin >> n;
aarr[n] = i;
}
for (int i = 0; i < N; i++) {
cin >> barr[i];
carr[i] = aarr[barr[i]];
}
dp.push_back(carr[0]);
int lis = 0;
for (int i = 1; i < N; i++) {
if (carr[i] > dp[lis]) {
dp.push_back(carr[i]), lis++;
}
else {
int lo = lower_bound(dp.begin(), dp.end(), carr[i]) - dp.begin();
dp[lo] = carr[i];
}
}
cout << lis + 1;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
BOJ 2638번 치즈 (0) | 2020.02.13 |
---|---|
BOJ 2636번 치즈 (0) | 2020.02.13 |
BOJ 1958번 LCS 3 (0) | 2020.02.12 |
BOJ 9252번 LCS2 (0) | 2020.02.12 |
BOJ 9251번 LCS (0) | 2020.02.12 |