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

문제링크 : https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
int arr[2001];
int dp[2001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
        dp[i]=1; //최소인원은 1
    }

    for(int i=1; i<N; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[j]>arr[i]) dp[i] = max(dp[i], dp[j]+1); //인원 갱신
        }
    }

    cout << N-*max_element(dp, dp+N); //전체-최대 인원 

}

 

전투력이 높은 순서대로 정렬이 되어야하기 때문에 이에 맞게 dp를 갱신시켜 준다.

현재위치 기준으로 앞에 있는 값들을 검토하여 더 크다면 dp의 값을 그전 dp + 1을 하여 증가시켜준다.

 

이렇게 구한 값은 최대 인원을 갱신한 것이고 우리가 구하는 것은 열외시킬 인원이기 때문에 전체 N에서 dp의 최대값을 빼준 것을 출력하면 된다.