[Algorithm]Baekjoon 7570번 :: 줄 세우기

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

7570번: 줄 세우기

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int dp[1000001] = { 0 };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    int continuousLIS = -1;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
 
        dp[num] = dp[num - 1] + 1;
        continuousLIS = max(continuousLIS, dp[num]);
    }
 
    cout << n - continuousLIS;
}

 

이전의 2631번 문제의 줄세우기랑 비슷해보이는 문제이다.

 

다만, 2631의 줄세우기는 학생들을 아무데나 이동시킬 수 있는 문제였지만 이번문제는 무조건 맨 앞이나 맨뒤로만 이동시킬 수 있다.

그렇기때문에 우리는 그냥 lis가 아니라, 연속된 lis를 구해야 한다.

연속된 lis를 구해야하는거라서 오히려 코드는 굉장히 간단해진다. 특정수의 왼쪽에는 반드시 특정수-1이 있어야하기 때문이다.