[백준] 14003번 : 가장 긴 증가하는 부분 수열 5

문제

 

---

풀이

 

난이도는 플레티넘이지만 이전에 푼 2문제를 합치면 쉽게 풀 수 있어서 풀었다.

 

myunji.tistory.com/324?category=1154147

[백준] 14002번 : 가장 긴 증가하는 부분 수열 4

이 문제에서 수열을 출력해보았고

 

myunji.tistory.com/270

[백준] 12015번 : 가장 긴 증가하는 부분 수열 2

이 문제에서 이분 탐색으로 시간 복잡도를 O(nlogn)으로 줄였기 때문이다.

 

그래서 그냥 14002번 코드에서 arr[i][0]이 들어가야 할 위치를 lower bound로 찾아서 반환하는 것으로 수정했다.

---

소스코드

 

#include <iostream>
#include <stack>

using namespace std;

int arr[1000001][2], dp[1000001]; //arr[i][1] = k, i번째 원소의 최장 길이 수열의 길이는 k
stack<int> result;

int lowerBound(int left, int right, int key) { //lower bound를 찾는 함수
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dp[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right + 1;
}

int lis(int n) {
    int length = 0;

    for (int i = 1; i <= n; i++) {
        int pos = lowerBound(1, length, arr[i][0]); //arr[i][0]이 들어가야 할 위치 반환
        dp[pos] = arr[i][0];
        arr[i][1] = pos;
        if (pos > length) //증가 수열의 길이가 증가하는 상황
            length++;
    }
    int tmp = length; //길이 임시 저장
    for (int i = n; i >= 1; i--) {
        if (arr[i][1] == tmp) { //인덱스 확인하며 스택에 투입
            result.push(arr[i][0]);
            tmp--;
        }
    }
    return length;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i][0];
    cout << lis(N) << '\n'; //길이 출력
    while (!result.empty()) { //수열 출력
        cout << result.top() << ' ';
        result.pop();
    }
}

c++ 내장 lower bound 함수가 있지만, 직접 구현해야 까먹지 않을 것 같아서 직접 작성했다.

pos > length보다 크다는 뜻은 arr[i][0]이 dp의 어떤 원소보다 큰 최대 원소라는 뜻이기 때문에 length++를 한다.