가장 긴 증가하는 부분 수열

가장 길게 증가하는 수열의 길이만 구하면 되는 문제였기 때문에 lower_bound를 이용해서 문제를 해결하였습니다.

가장 긴 증가하는 부분 수열(1, 2, 3) 모두 범위만 다를 뿐 같은 결과를 구하는 문제였기 때문에 아래 코드로 모두 통과하였습니다.

lower_bound의 시간 복잡도가 log이기 때문에 전체 시간 복잡도는 O(NlogN)만에 해결할 수 있었습니다.

 

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

int main(void)
{
    int N, answer = 987654321, num;
    cin >> N;
    vector<int> vec;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        vector<int>::iterator iter;
        iter = lower_bound(vec.begin(), vec.end(), num);
        if (vec.size() == 0) vec.push_back(num);
        else if (iter == vec.end()) vec.push_back(num);
        else vec[iter - vec.begin()] = num;
    }
    cout << vec.size() << endl;
    return 0;
}

 

www.acmicpc.net/problem/11053

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

www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3