[Algorithm] Baekjoon 2631번 : 줄세우기

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

2631번: 줄세우기

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, input;
    int dp[201] = { 0 };
    vector<int> childs;
    int maxNum = 0;
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        childs.push_back(input);
    }
    
    for (int i = 0; i < childs.size(); ++i)
    {
        dp[i] = 1;
 
        for (int j = 0; j < i; ++j)
        {
            if (childs[i] > childs[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        maxNum = max(maxNum, dp[i]);
    }
 
    cout << n - maxNum;
}

최대한 아이들의 위치를 바꾸지 않고 정렬시키는 문제다.

그러면 주어진 줄 순서에서 최대한 오름차순상태인 아이들은 안건드리는 상태에서 나머지 아이들을 옮겨야 한다.

여기서 오름차순? 이면 바로 LIS가 생각날 것이다.

결국 이문제는 LIS를 구하고 전체에서 LIS값을 빼주면 된다.

 

LIS는 최장증가부분수열이다.즉, 가장 긴 오름차순의 형태이기 때문에 그 형태를 제외한 나머지 아이들만 옮겨주면 

최소의 교체로 오름차순을 만들 수 있다.