[BOJ] 13711 : LCS 4

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

---

DP 동적프로그래밍

[ 알고리즘풀이 ]

 입력으로 주어지는 배열 B의 Index를 A 배열을 기준으로 정렬하면 LIS 문제로 바뀌게 된다.

  Sorted배열 [ 3 0 4 1 2 5 ] 에서 가장 긴 LIS는 [ 0 1 2 5 ] 가 되고 이는 다시 생각해보면 B배열의 0, 1, 2, 5 인덱스이므로 실제 B배열에서 [ 1 4 5 6 ] 을 의미한다.

( O(NlogN) 으로 LIS구하기 :  https://travelbeeee.tistory.com/455?category=800452) 

 

[ 코드 C++ ]

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int LIS(vector<int> v) {
    const int INF = 99999999;
    int N = v.size();
    vector<int> Dp(N + 1, INF);
    int longest = 1;
    Dp[0] = -INF;
    Dp[1] = v[0];
    for (int cur : v) {
        if (Dp[longest] < cur) {
            longest++;
            Dp[longest] = cur;
        }
        else {
            vector<int>::iterator it = lower_bound(Dp.begin(), Dp.end(), cur);
            *it = cur;
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++)
        if (Dp[i] != INF) ans = i;
    return ans;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    cin >> N;
    
    vector<int> A(N);
    vector<int> temp(N);
    vector<int> index(N);
 
    for (int i = 0; i < N; i++)
        cin >> A[i];
 
    for (int i = 0, x; i < N; i++) {
        cin >> x;
        temp[x - 1] = i;
    }
 
    for (int i = 0; i < N; i++)
        index[i] = temp[A[i] - 1];
 
    cout << LIS(index);
    
}

[ github]

https://github.com/travelbeeee/BOJ/blob/master/BOJ13711.cpp

---