백준 - 12738 가장 긴 증가하는 부분수열

 

이 문제는 특정한 사정으로 다시 한번 공부하게 되었는데 다른 사람들의 코드를 조금더 쉽게 풀어서 작업하였다.

 

#include<bits/stdc++.h>

#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main() {
    Fast;
    int n;
    cin >> n;

    vector<int> arr;

    for (int i = 0; i < n; i++) {
        int in;
        cin >> in;
        if (arr.size() == 0) {
            arr.push_back(in);
        }
        else {
            int index = lower_bound(arr.begin(), arr.end(), in) - arr.begin();
            if (index == arr.size()) {
				arr.push_back(in);
			}
            else {
				arr[index] = in;
			}
        }
    }
    
    cout << arr.size() << endl;
    return 0;
}

 

후기

시험만 보면 왜이렇게 머리가 안돌아갈까..