[백준 알고리즘] 2631번: 줄세우기

https://www.acmicpc.net/problem/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명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이

LIS 알고리즘을 통해 최장 증가 부분 수열의 길이를 찾아주면 해당 숫자들을 제외한 나머지 숫자들만 옮겨주면 된다. LIS 알고리즘을 까먹어서 블로그에 이전에 정리해둔 글을 참고하고 문제를 풀었는데, 다시 정리하면 LIS는 다음과 같이 동작한다.

1. 처음부터 인덱스를 하나씩 기준점으로 만든다.
2. 만약 기준점의 lis 값이 0 이라면, 즉 한번도 갱신된 적이 없다면, 해당 값을 1로 갱신한다. 어떤 숫자의 최장 증가 수열은 최소한 1이기 때문이다.
3. 현재 기준점을 기준으로 이전까지 현재 기준점 값보다 작은 값들이 있는지 확인한다. 만약 있다면, 증가 수열을 만들 수 있다는 의미이므로 해당 값의 lis 값을 확인한다.
4. 확인한 lis 값에 1을 더했을 때, 현재 기준점이 가지고 있는 lis 값보다 작다면 lis 를 업데이트 하면 안된다. 우리가 원하는건 최장 증가수열익디 때문이다. 현재 lis 보다 더 클 때만 업데이트 한다.
5. 모든 값들을 기준으로 삼아 2~4 알고리즘을 반복하고 lis 값이 업데이트 될 때마다 최대 값인지 확인해서 최대값을 기록한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

    vector<int> kids;
    vector<int> dp (N, 0);
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        kids.push_back(n);
    }

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

    cout << N - lis;

}