BOJ 3745번 오름세

BOJ : https://www.acmicpc.net/problem/3745

github : https://github.com/junho0956/Algorithm/blob/master/3745/3745/%EC%86%8C%EC%8A%A4.cpp

 

dp의 한 종류인 lis 알고리즘과 파일의 끝을 판별하는 법을 사용할 줄 안다면 문제를 해결할 수 있습니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
 
int N;
vector<int> dp;
int arr[100001];
 
int main() {
 
    while (scanf("%d", &N) != EOF) {
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
        dp.clear();
 
        dp.push_back(arr[0]);
        int lis = 0;
 
        for (int i = 1; i < N; i++) {
            if (arr[i] > dp[lis]) {
                dp.push_back(arr[i]);
                lis++;
            }
            else {
                int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
                dp[lo] = arr[i];
            }
        }
 
        printf("%d\n", lis + 1);
    }
 
    return 0;
}