[BaekJoon 14003번] 가장 긴 증가하는 부분 수열 5(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

14003번: 가장 긴 증가하는 부분 수열 5

 

 

[문제 설명]

 

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

[입력]

 

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

 

[출력]

 

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
6 10 20 10 30 20 50	4 10 20 30 50

 

 

[문제 풀이]

 

 

아래 포스트에서 O(nlongn) 최장 증가 부분 수열 구하기 내용을 작성하여

포스트로 설명을 대체하도록 하겠습니다.

[Algorithm] 최장 증가 부분 수열(LIS)

 

아래 문제는 입력 범위가 더 작습니다. 같이 풀어보면 좋습니다.

14002번: 가장 긴 증가하는 부분 수열 4

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

vector<int> LIS;
vector<int> ans;
vector<pair<int, int>> backtrace;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N; // 수열의 크기
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        if(LIS.empty()) {
            LIS.emplace_back(n);
            backtrace.push_back({LIS.size() - 1, n});
        } else {
            if(LIS.back() < n) {
                LIS.emplace_back(n);
                backtrace.push_back({LIS.size() - 1, n});
            } else {
                auto location = lower_bound(LIS.begin(), LIS.end(), n);
                LIS[location - LIS.begin()] = n;
                backtrace.push_back({location - LIS.begin(), n});
            }
        }
    }
    cout << LIS.size() << '\n';
    int len = LIS.size() - 1;
    for(int i = N -1; i >= 0; --i) {
        if(backtrace[i].first == len) {
            len -= 1;
            ans.emplace_back(backtrace[i].second);
        }
    }

    sort(ans.begin(), ans.end());
    for(int element : ans) {
        cout << element << ' ';
    }
   
    return 0;
}