BOJ 11568번 민균이의 계략

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

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

 

일반적인 dp 중 한 부류인 lis 알고리즘으로 해결할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[1001];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    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];
        }
    }
 
    cout << lis + 1;
    return 0;
}