[백준] 2550 전구, 비슷한 유형

 

문제

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

가장 긴 증가하는 부분 수열 5: https://www.crocus.co.kr/681

전기줄2: https://www.acmicpc.net/problem/2568

 

 

전구 문제 자체는 N < 10,000 으로, O(N^2)으로 풀이해도 1억 연산 내외로 풀이는 가능하다.

LIS 경로추적을 처음 풀어봐서 고생했다.

vector<int> path로 LIS 추가 시 마다, 같이 기록하면서 LIS의 길이를 구하고, 역추적 해주면 된다.

전기줄, ab/a/b

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int a[10011];
int b[10011];
int bb[10011];
int ab[10011];
vector<int> dp;
vector<int> path;
vector<int> ret;
int main()
{
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) {
        cin >> b[i];
        bb[b[i]] = i;
    }

    // 스위치와 전구를 연결
    for (int i = 0; i < N; ++i) ab[i] = bb[a[i]];

    // 카운트
    int end = 0;
    // 처음은 일단 push
    dp.push_back(ab[0]);
    path.push_back(0);

    // 이분 탐색
    for (int i = 1; i < N; ++i)
    {
        // 가장 뒤에 있는 값이, 현재 값 보다 작을 때는 push 
        if (dp.back() < ab[i]) {
            dp.push_back(ab[i]);
            path.push_back(++end);
        }
        else {
            // 값이 들어갈 곳을 찾아 넣어줌, 해당 값에 대응되는 level(it-dp.being())도 push 
            auto it = lower_bound(dp.begin(), dp.end(), ab[i]);
            *it = ab[i];
            path.push_back(it - dp.begin());
        }
        cout << "path : "; for (int j = 0; j < path.size(); ++j) cout << path[j] << " "; cout << "\n";
    }

    // 경로 추적
    int flag = end;
    for (int i = N - 1; i >= 0; i--) {
        if (path[i] == flag)
        {
            ret.push_back(b[ab[i]]);
            flag--;
        }
        if (flag == -1) break;
    }

    sort(ret.begin(), ret.end());
    cout << ret.size() << "\n";
    for (int i : ret) cout << i << " ";
    return 0;
}

 

path 출력