[2550번] 전구

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘 :: http://www.crocus.co.kr/583

2. LIS 추적 :: http://www.crocus.co.kr/681

전형적인 LIS 추적 문제이다.

이 문제는 [2568번] 전깃줄 - 2 :: http://www.crocus.co.kr/872 와 동일한 문제이다.

첫번째 들어오는 인풋을 LIS를 위해 인덱싱을 다시 0번부터 지정해주고

두번째 들어오는 인풋은 들어오는 값에 대한 첫번째 값과 대응되도록 해당하는 인덱스를 부여해준다.

그렇게해서 LIS를 돌리고, LIS 추적을 돌리면 답을 구할 수 있다.

나머지 내용은 주석을 통해 몇가지 이야기를 해두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int MAX = 987564321;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<int> idx(n + 1); // val이 가지는 idx
    vector<int> rev(n + 1); // idx가 가지는 val
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        idx[val] = i;
        rev[i] = val;
    }
 
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[i] = idx[val];
    }
 
    vector<int> lis(n, MAX);
    vector<pair<int, int> > trace;
 
    int plis = 0;
 
    lis[0] = arr[0];
    trace.push_back({ 0, arr[0] });
 
    for (int i = 1; i < n; i++)
    {
        // lis 인덱스 검출
        auto it = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
 
        lis[it] = arr[i];
 
        trace.push_back({ it, arr[i] });
    }
    
    // plis = lis 크기
    int len = lis.size();
    for (int i = 0; i < len; i++)
        if (lis[i] != MAX)
            plis++;
 
    plis--; // 인덱스 0부터 시작이니 -1
 
    len = trace.size();
    
    // 역추적
    vector<int> ansIdx;
    for (int i = len - 1; i >= 0; i--)
    {
        if (trace[i].first != plis)
            continue;
    
        ansIdx.push_back(trace[i].second); // idx가 담긴다.    
        plis--;
    }
 
    vector<int> ans;
 
    // idx를 다시 실제 값으로 변환
    len = ansIdx.size();
    for (int i = 0; i < len; i++)
        ans.push_back(rev[ansIdx[i]]);
 
    // 오름차순
    sort(ans.begin(), ans.end());
 
    printf("%d\n", ans.size());
    for (auto i : ans)
        printf("%d ", i);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>