[BOJ / C++] 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 이하의 정수이다.

출력

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

Solved.ac 레벨

골드 IV

풀이

문제와 '다이나믹 프로그래밍'이라는 분류를 번갈아 가면서 보고, 나름대로 예제를 만들어서 줄도 세워보는데 문제를 어떻게 DP로 접근해야 하는지 감조차 잡히지 않았다. 내 블로그에서 그동안 풀었던 DP 문제들을 보며 이것저것 고민하다가 LIS를 구글에 검색했는데 나무위키에서 LIS를 줄 세우기에 활용할 수 있다는 사실을 알았고 LIS의 길이를 구해 전체 인원 수에서 빼주면 된다는 것을 알았다.

 

문제에서는 4명이 움직여서 정렬이 가능하다고 했으나 이를 다르게 바라보면 움직이지 않아도 되는 3명을 구하면 되는 문제다.

이미 오름차순인 최장 증가 부분 수열을 제외한 사람들만 움직이면 되므로 LIS를 구하면 되는 것이다.

 

LIS를 구하는 과정은 간단하다.

dp[i]에 들어가는 값은 kids[i]의 어린이를 마지막으로 하는 LIS의 길이다. 따라서 초기에는 모든 어린이를 마지막으로 하는 LIS를 구하면 되므로 dp 배열을 모두 1부터 초기화를 진행했다.

 

LIS를 구하는 과정은 코드에 주석으로 달아두었다.

Code

#include <bits/stdc++.h>

using namespace std;

int n, ans = 0;
int kids[201];
int dp[201];

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

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> kids[i];
        dp[i] = 1;
    }


    //dp[i] => kids[i]를 마지막 수로 하는 LIS의 길이
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(kids[j] < kids[i]) {
                //현재 어린이의 번호보다 이전 어린이의 번호가 작아야 부분 증가수열이 성립한다.
                //i번째 어린이를 마지막으로 하는 LIS의 길이, j번째 어린이를 마지막으로 하는 부분 증가수열의 길이 중 큰 값을 저장
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << n - ans << "\n";

    return 0;
}

2631번: 줄세우기