[백준/Baekjoon] 14003 가장 긴 증가하는 부분 수열 5 C++ :: LIS

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

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

---

1. Logic

- 기본 구성은 가장 긴 증가하는 부분수열 2, 3과 똑같다. 하지만 여기서는 역추적을 통해 LIS가 어떻게 구성되었는지 경로를 출력해야한다.

 

경로를 갱신해 줄 때 아무값이나  막 넣어주면 안되기 때문에 첫번째로 LIS인 수열에 대해서 입력해준다. 즉 이전에 들어간 숫자보다 더 큰 숫자가 나올경우 경로를 갱신해준다. 만약 이전에 들어간 숫자보다 작은 숫자가 나올경우 다시 처음부터 세줘야하는데 이때 우리가 lower_bound 또는 이분탐색으로 얻은 인덱스 값을 trace배열에 갱신해 주는 것이다.

예제로 보자면 

input : 10 20 30 21 40 에 대해서

10 trace[0] = 0

20 trace[1] = 1

30 trace[2] = 2

21 trace[3] = 2 >> 21보다 같거나 큰 위치가 input의 2번째 인덱스이기 때문에 2를 넣어준다.

40 trace[4] = 3

이렇게 값을 넣어주고 뒤에서부터 추적해준다. 그렇게 되면 3 > 2 > 1 > 0순으로 되기 때문에 답을 reverse로 출력해주면 답은 2가지가 나올 수 있다. {10 20 30 40} {10 20 21 40} 하지만 둘다 정답이기 때문에 어떠한 답을 출력하더라도 상관은 없다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int cnt = 0;

vector<int> input;
vector<int> lis;
int trace[1000001];

int binarySearch(int key) {
    int start = 0;
    int end = lis.size() - 1;

    int mid;
    while(start < end) {
        mid = (start + end) / 2;

        if(key > lis[mid]) {
            start = mid + 1;
        }
        else 
            end = mid;
    }
    return end;
}

void solve() {
    for(int i = 0; i < n; i++) {
        if(lis.empty() || lis.back() < input[i]) {
            trace[i] = cnt;
            lis.push_back(input[i]);
            cnt++;
        }
        else {
            int idx = binarySearch(input[i]);
            lis[idx] = input[i];
            trace[i] = idx;
        }
    }
    cout << cnt << "\n";
}

void print() {
    vector<int> tra;
    int tr = cnt - 1;
    for(int i = n-1; i >= 0; i--) {
        if(trace[i] == tr) {
            tra.push_back(input[i]);
            tr--;
        }
    }

    for(int i = tra.size() - 1; i >= 0; i--) {
        cout << tra[i] << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;

    for(int i = 0; i < n; i++) {
        int a; 
        cin >> a;
        input.push_back(a);
    }

    solve();
    print();
}

---

 

 

3. Feedback

역추적 하는 과정을 생각하면서 단순히 갱신할 때만 넣어주면 된다고 생각했는데 구현하는 과정에서 매끄럽게 되지 않아서 고전했다. 역추적을 하는 방법을 조금 더 구현해봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐