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

[ 문제 ]

 

2631번: 줄세우기

 

[ 접근방법 ]

 

전체에서 순서를 바꾸지 않아도 되는 번호를 빼주는 방식으로 풀었다.

 

즉, 최장 증가 부분 수열( LIS )의 길이를 구하고 n에서 빼주면 된다.

 

dp[ i ] = i + 1번째 수를 끝으로 하는 LIS의 길이.

 

위와 같이 dp를 설정하고 2중 for문을 돌면서 값을 갱신한다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>

using namespace std;

int n, maxLength;
vector<int> vec, dp;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    vec.resize(n);
    for(int i = 0; i < n; i++)cin >> vec[i];

    dp.assign(n, 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(vec[j] < vec[i] && dp[j] >= dp[i]){
                dp[i] = dp[j] + 1;
            }
        }
        if(maxLength < dp[i])maxLength = dp[i];
    }

    cout << n - maxLength;

    return 0;
}