[13711번] LCS 4

문제 출처 :

https://www.acmicpc.net/problem/13711

알고리즘 분석 :

문제 해결에 필요한 사항

1. LCS :: http://www.crocus.co.kr/787

2. LIS :: http://www.crocus.co.kr/583

LCS 4 문제를 풀기전 

LCS 시리즈를 풀어보고 :: http://www.crocus.co.kr/search/lcs 

LIS 시리즈를 풀어본 뒤 :: http://www.crocus.co.kr/search/lis

두개의 개념을 이해하고 풀면 좋을 것 같다.

이 문제에서는 A, B 배열을 주고, 그에 맞는 LCS를 구하라고 하고 있다.

이때 LCS를 풀기위해 2차원 배열로 풀게 된다면 N의 최대가 100,000이기에 메모리 초과와 시간 초과를 둘다 받을 수 있다.

그렇다고 LCS에서 사실 길이를 구하기 위해 모든 배열이 필요는 없기에

메모리 최적화를 통해 변수들만으로 해결하려 해도 TLE를 받게 되있다.

여기서 주어진 단서는 N 크기의 배열에는 1~N의 번호만 들어온다고 되어있다.

따라서 이것을 이용하여보자.

아래 그림을 이용하여 생각해보자.

처음 A배열에 입력받는 값을 인덱스라고 생각하고 다시 A배열을 생성하면

pos라는곳에 받아서 저 pos를 토대로 A 배열을 만들면 3번째 장면과 같아진다.

(사실 그냥 처음 입력받은 A배열을 인덱스라 생각하고 다시 A배열을 만든 것이다.)

결국 이 값을 토대로 AB[i] = A[B[i]]를 만들어주게 된다면

AB에 대한 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <iostream> #include <cstdio>   using namespace std;   int a[100010]; int b[100010]; int ab[100010];   int lis[100010];   int _lower_bound(int start, int end, int target) {     int mid;       while (start < end)     {         mid = (start + end) / 2;           if (lis[mid] < target)             start = mid + 1;           else             end = mid;     }       return end + 1; }   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int pos;         scanf("%d", &pos);           a[pos - 1] = i;     }     for (int i = 0; i < n; i++)     {         scanf("%d", &b[i]);         b[i]--;           ab[i] = a[b[i]];     }       int pArr = 1;     int pLis = 0;          lis[0] = ab[0];       while (pArr < n)     {         if (lis[pLis] < ab[pArr])             lis[++pLis] = ab[pArr];           else         {             int ans = _lower_bound(0, pLis, ab[pArr]);             lis[ans - 1] = ab[pArr];         }           pArr++;     }       printf("%d", pLis + 1);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus