[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를 구해야 한다.

그 이유로는 다음과 같다.

 

이번 문제같은 경우는, 맨 앞이나 뒤로만 이동 가능하기 때문에 단순히 증가하는 부분 수열을 선택하면 해결이 불가능하다.

2 1 3 5 4 6 과 같은 예시를 생각해보자.

 

해당 예시에서는 2,3,4가 연속된 최장 증가 부분 수열이다.

연속된 3개의 수 이외의 수만 이동시켜 주면 정렬이 가능하기 때문에 연속된 수는 맨 앞이나 맨 뒤로 이동할 이유가 전혀 없다.

따라서 나머지 수를 각각 한 번씩만 이동시켜주면 해결이 가능하다. 

ex) 1 2 3 5 4 6 -> 1 2 3 4 6 5 -> 1 2 3 4 5 6

 

즉, 결국 '연속된' LIS의 최대길이를 구하는게 관건이다. (위 예시의 2,3,4처럼 '연속'되어야 한다. 그래서 6은 포함하지않는다)

 

이 연속된 LIS길이를 구하기위해 본문의 코드처럼 수행한다. 뭔가 굉장히 복잡할 거 같지만, 본문코드를 보면 알 수 있듯이 매우 간단하다.

dp[num] = dp[num-1] + 1 이 기본적인 로직인데, 이게 되는 이유는 일단 연속되어야하고, 자신의 숫자 -1인 숫자가 이전에 등장했어야만 하기 때문이다.

그래서 그냥 dp[num-1]에 +1을 한 값이 현재 숫자의 연속된 lis가 될 수 있다.