[백준] 18353 병사 배치하기

문제

전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치

입력

N (1 ≤ N ≤ 2,000)
각 병사의 전투력은 10,000,000보다 작거나 같은 자연수

출력

남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력

풀이

남아있는 병사의 수가 최대가 되기 위해서는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 찾기
즉, 증가하는 부분이 가장 크도록 만드는 수를 찾아서 전체 병사의 수(N)-LIS의 값이 열외시켜야 하는 값

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define MAXN 2001
int N;

vector<int> arr;
int main(){
    cin>>N;
    int temp;
    for(int i=0;i<N;i++){
        cin>>temp;
        arr.push_back(temp);
    }
    
    reverse(arr.begin(),arr.end()); //뒤에서부터 증가하는 부분 찾기
    
    int dp[2000]; //LIS를 찾으면서 증가하는 부분의 수 저장 배열
    fill(dp,dp+2000,1); //배열 1로 초기화
    
    //LIS 찾기
    for(int i=1;i < N; i++){
        for(int j=0;j < i; j++){
            if(arr[i]>arr[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    
    int maxCnt=0;
    
    for(int i=0;i<N;i++){
        maxCnt=max(maxCnt,dp[i]); //LIS의 최대값 찾기
    }
    
    cout<<N-maxCnt<<"\n"; //열외시켜야하는 수
    

    
    return 0;
}