[C++] BOJ 18353번: 병사 배치하기

ㅎㅎ·2023년 7월 8일
0

BOJ

목록 보기
23/65

BOJ 18353번: 병사 배치하기

문제

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.


문제 풀이 - 성공

LIS(최장 증가 부분 수열) 알고리즘과 DP를 사용

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

int arr[2001];
vector<int> v;

int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int n, num, i, maxnum = 0;
    cin >> n;

    for (i = 0; i < n; i++) { // 입력 받기
        cin >> num;
        v.push_back(num);
    }
    reverse(v.begin(), v.end()); // 뒤집어서 오름차순 구하는 형식으로 바꾸기

    for (i = 0; i < n; i++) { // LIS
        arr[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                arr[i] = max(arr[i], arr[j] + 1); // 값 업데이트
            }
        }
    }

    for (i = 0; i < n; i++) { // 최댓값
        maxnum = max(maxnum, arr[i]);
    }
    cout << n - maxnum;

    return 0;
}

profile
Backend

0개의 댓글