백준 2631 - 줄세우기

문제 설명

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1부터 N까지 무작위로 정렬된 번호가 주어지면 이를 오름차순으로 정렬하기 위해 번호의 위치를 조정할 때 최소한으로 움직이는 이동 횟수를 구하는 것이다.

 

접근법을 생각했을 때, 확신이 생기는 방법이 없었다.

N이 200이하이기 때문에 모든 번호를 하나씩 옮겨보는 방법도 생각해 봤고 결과적으로 자신의 위치가 정해져 있기 때문에 해당 위치로 옮기는 방법을 생각해 봤는데 언제나 최적해를 구할 수 없었다.

결과적으로 최적해를 구하기 위해서는 바꿔야하는 수가 아닌 바꾸지 않아도 되는 수를 구하면 되는 것이다.

바꾸지 않아도 되는 수는 자신보다 작은수보다는 뒤에 있으며 자신보다 큰 수보다는 앞에 있는 번호들이다.

즉, 최장 증가 부분 수열을 구하면 된다.

예를 들어 보자.

빨간 부분은 최장 증가 부분 수열을 나타낸 것이다.

빨간 부분은 빨간 부분끼리 알맞은 순서로 정렬되어 있는 상태이다.

따라서, 이들끼리는 이동시킬 필요가 없다.

또한, 이는 최장 증가 부분 수열이기 때문에 이것보다 적게 수를 움직여 정렬이 불가능하다.

즉, 전체에서 LIS의 길이를 뺀다면 정답을 구할 수 있다.

 

LIS는 DP를 통해 쉽게 구할 수 있다.

만약 자신보다 앞에 있는 수가 자신보다 작다면 해당 부분까지의 LIS에 자신을 더해 새로운 LIS를 만들 수 있다.

for (int i = 1; i < N; i++)
{
    for (int j = 0; j < i; j++)
    {
        if (children[j] < children[i])
        {
            dp[i] = max(dp[i], dp[j]+1);
        }
    }

    ans = min(ans, N - dp[i]);
}

LIS를 구했다면 전체에서 빼 정답을 가장 작은 수로 갱신한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;
vector<int> children;
vector<int> dp;

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

    cin >> N;
    children.resize(N);
    dp.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> children[i];
        dp[i] = 1;
    }

    //make LIS
    int ans = N;
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (children[j] < children[i])
            {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }

        ans = min(ans, N - dp[i]);
    }

    cout << ans;

    return 0;
}

---