백준 2631번 : 줄세우기

  처음에는 이 문제를 어떻게 풀어야 하나 싶었는데 사실 지금도 어떻게 풀어야 맞는 것인지는 모르겠다. ㅎㅎ;; 왠지모르게! 그냥! 최장길이증가수열(LIS)의 길이를 구한다음에 전체 길이에서 빼주면 그게 답이 되지 않을까? 라고 생각했다. 그냥 어렴풋한 생각으로는 번호 순서대로 서 있다는게 결국에는 증가수열로 서 있다는 것이기 때문에 

 

기존 수열에서 LIS를 구하고 LIS는 그대로 고정!

그리고 나머지를 올바른 위치로 샥샥 옮기면!

증가수열 완성!

 

예를 들어서 3 7 5 2 6 1 4 에서 LIS는 3 5 6이다. 따라서 남은 1 2 4 7을 자리에 맞춰서 샥샥 끼워맞추는 식이다.

 

#include <iostream>

using namespace std;

int n;
int seq[202];
int lis[202];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> seq[i];
    }
    
    int maxLen = 1;
    lis[0] = 1;
    for(int i = 1; i < n; i++)
    {
        lis[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(seq[j] > seq[i]) continue;
            lis[i] = max(lis[i], lis[j] + 1);
        }
        
        maxLen = max(maxLen, lis[i]);
    }
    
    cout << n - maxLen << "\n";
 
    return 0;
}