[백준/BOJ] 18353번 병사 배치하기 (C++)

www.acmicpc.net/problem/18353

18353번: 병사 배치하기

DP 유형의 문제로 LIS를 활용하는 문제입니다.

전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 하므로, 이를 뒤집어 오름차순으로 변경하고 LIS의 최대값을 구해 전체 병사의 수에서 빼주면 되는 문제입니다.

 

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

int dp[2001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 0;
    cin>>n;
    vector<int> v(n + 1);
    
    for(int i = 1; i <= n; i++) {
        cin>>v[i];
    }
    
    // 배열을 오름차순 비슷하게 만들기 위해 뒤집기(벡터를 1번 인덱스부터 사용하므로 +1)
    reverse(v.begin() + 1, v.end());
    
    // dp 배열을 1로 초기화
    fill(dp + 1, dp + 2001, 1);
    
    // LIS(Longest Increasing Subsequence) : 최장 증가 수열
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(v[i] > v[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    for(int i = 1; i <= n; i++) {
        answer = max(answer, dp[i]);
    }
    
    cout<<n - answer;
}