[백준 2631] 줄세우기 C++

문제

백준 2631

2631번: 줄세우기

풀이

먼저 LIS (최장 증가 부분 수열)을 구합니다.

LIS에 해당하지 않은 원소를 옮겨주면 되므로 n-LIS가 답이 됩니다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int dp[201];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    // 입력
    int n;
    cin >> n;
    int LIS = 0;
    vector<int> v;
    v.push_back(0);
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    // LIS 구하기
    for (int i = 1; i < v.size(); i++) {
        int temp = 0;
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                temp = max(dp[j], temp);
            }
        }
        dp[i] = temp + 1;
        LIS = max(LIS, dp[i]);
    }
 
    cout << n - LIS << endl;
    return 0;
}