[BOJ] 줄 세우기_2631 C++ 풀이

문제

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

예를 들어 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다면 3 7 5 2 6 1 4 먼저 4번 아이를 7번 아이의 뒤로 옮기고, 7번 아이를 맨뒤로 옮기고, 1번 아이를 맨앞으로 옮긴후 마지막으로 2번 아이를 1번 아이의 뒤로 옮기면서 번호 순서대로 아이들을 배치한다. 1 2 3 4 5 6 7

접근 방법

이 문제는 가장 큰 증가하는 부분수열의 개념을 이용하여 동적 계획법으로 접근하면서 입력된 수열에서 가장 큰 증가하는 부분수열의 크기만큼을 전체 수열의 크기에서 빼주어 최소 이동 횟수를 구하는 방식을 생각해 내었다.

하나의 수열에 속한 부분수열 중에서 가장 큰 증가하는 부분수열을 기준점으로 잡고 나머지 아이들을 옮겨준다면 원하는 출력값을 얻을수 있을거라 생각하였다.

예를 들어 예제의 3 7 5 2 6 1 4에서 가장 큰 증가하는 부분수열의 크기는 3 7 5 2 6 1 4. 즉 {3, 5, 6} 으로 3 이며 수열의 크기는 7 이므로 전체수열의 크기에서 부분수열의 크기를 빼준 4가 아이들의 최소 이동 횟수인 것을 알 수 있었다.

따라서 주어진 수열에서 가장 큰 증가하는 부분수열을 어떻게 구할 것인가가 관건이었는데 이를 동적 계획법을 활용하여 다음과 같이 구현하였다.

1. 주어진 수열 값들을 훑어가며 자기보다 이전 값들 중에서 더 작은 값들을 모두 비교한다.

2. 더 작은 값들 중, 해당 값을 선택했을 때, 증가하는 부분수열의 크기가 기존의 값보다 커지면 그 값으로 갱신하고 아니면 패스한다.

해당 부분수열의 크기를 저장하기 위해서 DP 배열을 사용하였다. i번 인덱스에 에 있는 값을 선택했을 때 DP$[$i$]$의 값은 곧 증가하는 부분수열의 크기를 의미한다.

3 7 5 2 6 1 4 수열의 인덱스를 1~7로 볼때, 첫 부분 3보다 이전의 값은 존재하지 않으므로 가장 큰 증가하는 부분수열의 크기는 1이된다. DP[1] = 1

그 다음 두번째 인덱스 7의 가장 큰 증가하는 부분수열의 크기는 {3, 7}, 즉 2가된다. DP[2] = 2

세번째 인덱스 5의 가장 큰 증가하는 부분수열의 크기는 {3, 5}, 즉 2가 된다. DP[3] = 2

네번째 DP[4] = 1이 되고 5번째 인덱스 6을 보게 되면 {3, 5, 6}, DP[5] = 3 이 된다.

3번째와 5번째 인덱스 최대 길이 구하는 과정에서 보는 바와 같이 {3, 5} -> {3, 5, 6} 즉 5번째 인덱스의 길이는 세번째 인덱스의 길이 + 1이 된다. 이런 식으로 최대 부분 수열의 길이를 구할 수 있다.

for(int i=1; i<=n; i++)
    {
        dp[i] = 1;
        for(int j=1; j<=i; j++)
        {
            if(children[j] < children[i] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
        }
        if(max < dp[i]) max = dp[i];
    }

구현

#include<iostream>
#include<vector>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    int max = 0; // 최대 증가 부분 수열 크기
    cin>>n;

    vector<int> children(n+1,0);
    vector<int> dp(n+1,0); // i번째 인덱스 값의 증가하는 부분수열의 크기를 저장

    for(int i=1; i<=n; i++) cin>>children[i];

    for(int i=1; i<=n; i++)
    {
        dp[i] = 1;
        for(int j=1; j<=i; j++)
        {
            if(children[j] < children[i] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
        }
        if(max < dp[i]) max = dp[i];
    }

    cout<<n-max;
    return 0;
}

BOJ_줄 세우기