티스토리 뷰

알고리즘 관련/BOJ

BOJ)13711 LCS4

JASON 자손9319 2017. 1. 22. 15:30

문제: icpc.me/13711


LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다.


하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다.


단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다.


1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다.


우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤


A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다.


이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로 LIS를 구해야 한다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 100000
using namespace std;
int a[MAX_N + 1], b[MAX_N + 1], x, n, r;
vector<int> vt;
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&x);
        a[x] = i;
    }
    for (int i = 1; i <= n; i++
        scanf("%d"&b[i]);
    vt.push_back(-MAX_N - 100);
    for (int i = 1; i <= n; i++) {
        if (vt.back() < a[b[i]]) {
            vt.push_back(a[b[i]]);
            r++;
        }
        else {
            auto it = lower_bound(vt.begin(), vt.end(), a[b[i]]);
            *it = a[b[i]];
        }
    }
    printf("%d\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2637 장난감조립  (0) 2017.01.22
BOJ)9470 Strahler 순서  (0) 2017.01.22
BOJ)13711 LCS4  (0) 2017.01.22
BOJ)1183 약속  (0) 2017.01.22
BOJ)2150 Strongly Connected Component  (0) 2017.01.21
BOJ)3176 도로 네트워크  (0) 2017.01.21
TAG
,
댓글
댓글쓰기 폼