백준18353 - 병사 배치하기

https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

LIS로 해결하면 되는 문제이다. 연속되게 작아지는 수열을 찾으면 되기 때문에 일반적인 LIS문제와 조금 다르지만 입력한 숫자에 마이너스를 붙여서 비교하면 내림차순도 찾을 수 있기 때문에 LIS로 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

int main() {
    int n, x;
    vector<int> v;
    
    v.push_back(INF);
    cin >> n;
    for(int i = 0 ; i < n; i++) {
        cin >> x;
        x = -x; //내림차순인 수열을 찾기 위하여 -를 붙임
        if(v.back() < x) {
            v.push_back(x);
        }
        else {
            auto it = lower_bound(v.begin(), v.end(), x);
            *it = x;
        }
    }
    cout << n - v.size();
    return 0;
}