BOJ 2631번 줄 세우기

BOJ : https://www.acmicpc.net/problem/2631

github : https://github.com/junho0956/Algorithm/blob/master/2631/2631/%EC%86%8C%EC%8A%A4.cpp

 

어떻게 푸는건지 감을 못잡았는데

문제 예시에서 움직이는 4, 7, 1, 2 를 제외한 3, 5, 6은 이미 정렬이 되어있는 상태였고

3, 5, 6 자체가 증가하는 부분수열이니

문제에서 가장 긴 증가하는 부분수열을 찾는다는 생각으로 lis를 구현하였다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N;
vector<int> dp;
int arr[201];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    dp.push_back(arr[0]);
    int lis = 0;
 
    for (int i = 1; i < N; i++) {
        if (dp[lis] < arr[i]) {
            dp.push_back(arr[i]);
            lis++;
        }
        else {
            int lo = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
            dp[lo] = arr[i];
        }
    }
 
    cout << N - (lis + 1);
    return 0;
}