BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이

문제를 읽고 이해하기

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

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

입력

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

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

출력

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

재정의와 추상화

BOJ 11053 - 가장 긴 증가하는 부분 수열 문제에서는 N의 범위가 작기 때문에 DP로 풀 수 있었지만 이 문제는 N의 범위가 100만으로 엄청 커져버려서 시간 제한 안에 풀 수 없다.

이 문제를 통해 범위가 바뀌면 알고리즘 자체가 바뀌어야 할 수도 있다는 것을 알게 되었다.

순차적으로 입력되는 수에 대해서 알고리즘은 아래와 같이 구성된다.

1. 입력받은 수가 벡터의 맨 뒤에 있는 수보다 클 경우 수를 맨 뒤에 집어 넣는다.
2. 그렇지 않을 경우, 이분 탐색의 lower_bound를 이용하여 입력받은 수보다 크거나 같은 값이 처음 위치한 곳(lower_bound의 리턴값)에 입력 값을 대치시킨다.

이를 구현하기 위해 처음 climits 헤더에 있는 INT_MAX값(2^31 - 1)을 벡터에 추가한다. 이는 처음 입력받은 수에 대해서 따로 for문 내부에서 예외처리를 하지 않고 lower_bound를 통해 첫 인덱스에 값을 대입하기 위함이다.

그리고, 이후에 들어온 입력값에 대해 알고리즘을 시행한다.

2020/04/03 - [언어/C, C++] - [C++ STL] upper_bound, lower_bound 알아보기

[C++ STL] upper_bound, lower_bound 알아보기

코드 작성

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

vector<int> v;

int main() {
    int n;
    cin >> n;
    v.push_back(INT_MAX);
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if (v.back() < input) {
            v.push_back(input);
        } else {
            *lower_bound(v.begin(), v.end(), input) = input;
        }
    }
    cout << v.size();
    return 0;
}