[이코테/DP/C++] 병사 배치하기 (최장 증가 부분 수열 알고리즘, LIS)

 최장 증가 부분 수열 알고리즘(Longest Increasing Subsequence, LIS)

#include <bits/stdc++.h>

using namespace std;
int n;
vector<int> arr;

int main(void) {

    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
    reverse(arr.begin(), arr.end());
    // DP 테이블 초기화 : arr[i]를 마지막 원소로 가지는 부분수열의 최대 길이
    int dp[2000];
    for(int i=0; i<n; i++) dp[i] = 1;
    // 가장 긴 증가하는 부분 수열(LIS) 알고리즘수행
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(arr[j] < arr[i]) // j가 i보다 앞쪽에 있고 값이 작을때
                dp[i] = max(dp[i], dp[j]+1); // j를 마지막으로 가지는 수열의 최대길이 + 1과 비교
        }
    }
    // 열외해야 하는 병사의 최소 수를 출력
    int maxValue = 0;
    for(int i=0; i<n; i++) maxValue = max(maxValue, dp[i]);
    // 가장 긴 수열의 길이 구해서 전체 길이에서 빼기
    cout << n - maxValue << endl;
}