백준 13711번 : LCS 4 - LIS

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

13711번: LCS 4

1. 문제설명

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

 

이 문제는 두 수열의 LCS 크기를 구하는 문제이다.

단 조건으로 두 수열은 모두 1부터 N 사이의 숫자로 이루어져 있음을 준다.

 

문제에서 주어진 N이 10만이므로 O(N^2) 알고리즘인 LCS 알고리즘을 이용하면

시간초과로 틀린다.

 

문제에서 주어진 조건 두 수열은 모두 1부터 N 사이의 숫자로 이루어져있음을 활용하면

이 문제를 LIS 알고리즘으로 해결할 수 있다.

 

LIS는 수열이 주어졌을 때 수열 내 가장 긴 증가하는 부분을 구하는 알고리즘이다.

LIS 알고리즘은 이진탐색을 활용하면 O(NlogN)의 시간복잡도로 문제를 해결할 수 있다.

 

단 이 문제를 LIS로 해결하는 것을 생각해내기가 조금 어렵다.

 

 

예를 들어 두 수열 A, B가 다음과 같다고 가정하자

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

 

이 경우에 LCS 알고리즘으로 테이블을 그리면 답은 다음과 같다.

 

LCS

정답은 여러가지가 존재할 수 있지만

LCS의 길이는 3이 나온다.

 

A와 B는 둘다 1부터 N의 숫자로 이루어져있다.

LCS는 공통 부분 문자열을 구하는 것이므로

A와 B의 숫자를 같은 것 끼리 동일하게 변환을 해도 동일하게 공통 부분 문자열을 구할 수 있다.

 

좀 더 쉽게 예시를 들면

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

를

 

다음과 같이 변환해도 동일한 길이의 공통 부분 문자열을 바꿀 수 있다.

A,B에서 같은 원소를 동일하게 변환했기 때문이다.

위와 아래는 숫자는 다르지만 LCS의 길이를 구하는 데 있어서 동일한 상태라 볼 수 있다.

 

A : 1 2 3 4 5 6

B : 6 2 4 3 5 1

 

4->1

5->2

6->3

1->4

2->5

3->6

(A에 존재한 원소를 기준으로 변환한 것이다.)

 

이렇게 되면 이제 B에서 LIS를 구해주면 

LIS중 하나로

6 2 4 3 5 1

가 나오게 되고 길이는 3이 된다.

 

 

즉 1부터 N까지의 범위를 갖는 두 수열의 LCS 길이를 구하기 위해

수열을 변환하고 LIS 길이를 구하면 답을 구할 수 있다.

 

 

---

2. 문제풀이코드

#include <bits/stdc++.h>

#define MX 100003
using namespace std;

int n;
int A[MX], B[MX];
int changeNum[MX];
vector<int> ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
    }
    for(int i=1; i<=n; i++){
        cin >> B[i];
    }

    //숫자 변환
    for(int i=1; i<=n; i++){
        changeNum[A[i]] = i;
    }
    for(int i=1; i<=n; i++){
        B[i] = changeNum[B[i]];
    }

    //Lis
    for(int i=1; i<=n; i++){
        int idx = lower_bound(ans.begin(), ans.end(), B[i]) - ans.begin();
        if(idx == ans.size()){
            ans.push_back(B[i]);
        }else{
            ans[idx] = B[i];
        }
    }

    cout << ans.size() << '\n';
    return 0;
}