(C++) - 백준(BOJ) 18353번 : 병사 배치하기

https://www.acmicpc.net/problem/18353

18353번: 병사 배치하기

dp(lis) 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 n, 각 병사의 전투력을 저장할 일차원 배열 soldier, 가장 긴 내림차순의 길이를 저장할 일차원 배열 d를 선언합니다.

 

📔 풀이과정

길이는 1로 시작하기 때문에 모든 d배열의 원소를 1로 초기화합니다.

 

 1. 두 병사를 나눕니다. i와 j번째 병사를 선택합니다. 가장 뒤에 있는 병사까지 확인하기 전에 앞에 있는 병사들의 정답들이 뒤쪽으로 정답이 쌓이는 형상을 생각해봅니다. j는 앞에 있는 병사 i는 뒤에 있는 병사입니다.

 

 2. j병사가 i병사보다 전투력이 높다면 i번째까지 확인했을 때 가장 긴 내림차순의 길이는 max(d[i], d[j] + 1) 입니다. 이렇게 j 즉 앞쪽에 있는 병사가 i와 비교했을 때 전투력이 높다면 d[i]에 최댓값을 쌓아가는 방식으로 전체 답을 구할 수 있습니다.

 

 3. 마지막에는 가장 긴 d값을 저장합니다. 열외해야되는 병사의 수를 구해야 하기 때문에 n - 가장 긴 수열이 정답이 됩니다.

 

📔 정답출력

n - 가장 긴 전투력 내림차순의 길이를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, soldier[2001], d[2001];

int main(){
    cin >> n;
    memset(d,1,sizeof(d));
    for(int i = 0; i < n; i++) cin >> soldier[i];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++)
            if(soldier[j] > soldier[i])
                d[i] = max(d[i],d[j] + 1);

    int maxN = 0;
    for(int i = 0; i < n; i++) maxN = max(maxN, d[i]);
    cout << n - maxN;
}