[BOJ] 18353번 : 병사 배치하기

문제 링크 : 백준 18353번

[문제 접근]

어디선가 많이 본 문제이다. 가장 긴 증가하는 부분수열에서 증가가 아니라 감소로 바꾸면 된다.
가장 긴 감소하는 부분수열의 크기를 구하고 n에서 빼주면 열외해야 하는 병사의 수를 구할 수 있다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
int arr[2001];
int dp[2001];

int main(){
    cin >> n;
    for(int i=0 ; i<n ; i++) {
        cin >> arr[i];
    }
    for(int i=0; i<n ; i++) {
        int now=0;
        for(int j=0 ; j<i ; j++) {
            if(arr[i]<arr[j]) now = max(now, dp[j]);
        }
        dp[i] = now+1;
    }
    int ans=0;
    for(int i=0 ; i<n ; i++) {
        ans = max(ans, dp[i]);
    }
    cout << n-ans;

    return 0;
}