[C++] BOJ-2529

 

 

문제풀이

---

1. 기본적인 LIS(최장 증가 수열)를 찾는 문제이다.

 

2. 수열 v의 마지막 요소와 현재 입력받은 값을 비교하여 더 크면 v의 마지막에 넣고 그렇지 않으면 수열 v의 숫자들 중 가장 적당한 자리에 있는 숫자와 교체해준다.

 

3. 여기에서 적당한 자리라는 것은 만약 수열 v의 상태가 10, 30, 50 이고 현재 입력받은 값이 40이라면 50과 40을 교체한다.

 

(이 문제는 수열 그 자체를 구하는것이 아니라 수열의 길이를 구하는것이기 때문에 이러한 방식으로 숫자를 교체해주어도 답을 출력하는데에 지장은 없다.)

 

 

38분

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, ans = 0;
    cin >> N;
    
    int x = 0;
    
    vector<int> v;
    v.push_back(-1);
        
    for(int i = 0; i<N; i++){
        cin >> x;
        if(v.back() < x){
            v.push_back(x);
            ans++;
        }else{
            auto it = lower_bound(v.begin(),v.end(),x);
            *it = x;
        }
    }
    cout << ans;
}