[ 백준 2631 ] 줄 세우기 (C++)

백준의 줄세우기(2631) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 풀이보다는 문제의 해결방법을 찾는데 너무 시간이 오래 걸렸던 문제이다. 어떤식으로 접근했는지 차근차근 알아가보자.

   쉬운 예를 들어서 알아보자. 예를 들어, { 1, 2, 3, 4, 5 } 순서로 줄을 서 있는 아이들이 있다고 가정해보자. 이 아이들의 경우

   아이들이 애초에 순서대로 서있기 때문에 더 이상 옮겨주지 않아도 된다. 즉, 답은 0이 된다.

   그렇다면 { 5, 4, 3, 2, 1 } 의 경우는 어떻게 될까? 2,3,4,5 번 아이들을 순서대로 옮기면 순서에 맞게 줄이 이루어 지므로

   답은 4가 된다. 본인은 여기서 "가장 큰 증가하는 부분수열" 이 생각났다. Dynamic Programming의 방식으로 접근하면서 주어진

   수열에서 가장 큰 증가하는 부분수열의 크기만큼을 전체크기에서 빼주면 정답이 나올 것 같다는 생각이 들었다.

   왜냐하면, 하나의 수열에 속한 부분수열 중에서 가장 큰 증가하는 부분수열을 기준점으로 잡아버린다면, 나머지 아이들만

   옮겨주면 정답이 나올 것 같았다. 또한, 위에서 예로 든 { 1, 2, 3, 4, 5 } 의 경우, 가장 큰 증가하는 부분수열의 크기는 5이다.

   전체 5명에서 5를 빼버리면 0이라는 결과를 도출할 수 있었고, { 5, 4, 3, 2, 1 }의 경우 가장 큰 증가하는 부분수열의 크기는 1이기

   때문에 전체 5명에서 1을 뺀 4명을 옮기면 결국 답이 4가 되어 이런 방법을 생각해 보았다.

   실제로 예제입력1인 { 3, 7, 5, 2, 6, 1, 4 } 에서 가장 큰 증가하는 부분수열의 크기는 { 3, 5, 6 } 으로 3이되고, 전체 7 에서 3을

   빼면 4가 나오게 된다.

2) 그렇다면 가장 큰 증가하는 부분수열을 어떻게 구할지 알아보자.

   가장 큰 증가하는 부분수열이 어떤 수열을 말하는 것인지부터 차근차근 알아보자. 주어진 수열에서 부분 수열인데, 그 수열의

   규칙이 점점 증가하는 오름차순으로만 이루어진 수열을 의미한다.

   증가하는 부분수열을 구하는 방법은 이렇다.

   1. 자기보다 이전에 있는 값들 중에서 더 작은 값들을 모두 비교한다.

   2. 더 작은 값들 중, 해당 값을 선택했을 때, 증가하는 부분수열의 크기가 기존의 값보다 더 커지는지 비교한다.

   3. 2)의 결과로 기존의 값보다 더 커진다면, 그 값으로 갱신, 그게 아니라면 pass.

   본인은, 이 증가하는 부분수열의 크기를 저장하기 위해서 DP[] 라는 1차원 배열을 사용해주었다.

   DP[A] = B의 의미는 "A번 인덱스에 있는 값을 선택했을 때, 증가하는 부분수열의 크기는 B입니다." 가 된다.

   { 3, 7, 5, 4, 6, 2 } 라는 순열이 있다고 생각해보자. (제일 앞에서부터 1 ~ 6번 인덱스라고 가정)

   먼저 제일 앞에 '3'을 보자. 3보다 이전에 있는 값은 존재하지 않기 때문에, '3'일 때 가장 큰 증가하는 부분수열의 크기는

   1이 된다. 1이 되는 이유는 '3' 하나만으로도 부분수열이 되기 때문에 초기값은 1이 된다. DP[1] = 1.

   그다음 '7'을 보자. 7보다 이전에 있는 값들 중 더 작은 값으로는 '3'이 있고, '3'을 선택했을 때, DP[2]의 기존의 값인

   1보다 더 큰 값이 되기 때문에, '3'을 선택한다. 즉, DP[2] = 2가 된다. { 3, 7 } !

   '5'를 보자. 이전에 있는 값들 중 더 작은 값으로는 '3'이 있고, 이 값을 선택함으로써 DP[3]의 크기가 더 커질 수 있으므로 갱신 !

   DP[3] = 2.

   '4'의 경우, 윗줄에서 말한 '5'와 마찬가지로, { 3, 4 } 로 DP[4] = 2가 된다.

   '6'을 보자. 6보다 이전에 있는 값들 중 더 작은 값인 { 3, 5, 4 } 중에서, '3'을 선택한 경우를 생각해보자.

   현재 DP[5] = 1이다.('6'은 5번째 Index값) '3'을 선택하는 순간, DP[5] = 2가 된다. { 3, 5 } 가 되기 때문이다,.

   '5'를 선택하게 되면, DP[5] = 3이 된다. 결과적으로 보자면 { 3, 5, 6 }이 되기 때문이다.

   그렇다면, 여기서 값을 어떻게 비교하는지 체크해보자. DP[3]의 값은 2이다.('5'는 3번 Index값)

   그렇다면, DP[3] + 1의 값과, DP[5]의 값을 비교하게 된다.

   갑자기 무슨 말도 안되는 소리가 튀어나왔다는거 잘 알고있다. 현재 DP[3]은 2라는 값을 가지고 있다. 즉, 3번인덱스에서 가장 큰

   증가하는 부분수열의 크기는 2 입니다. 라는 의미를 가지고 있는데, '5'번 인덱스에서의 최대길이를 구하기 위해서

   '3'번 인덱스를 선택하게 되면, '3'번 인덱스의 최대길이 + 1이 되기 떄문이다.

   잘 생각을 해보자. 3번 인덱스인 '5'에서 최대길이는 2이다. 여기서 가장 뒤에 6이 붙으면 길이는 3이 될 것이다.

   { 3, 5 } -> { 3, 5, 6 } 이렇게 ! 즉, 5번 인덱스인 '6'에서 최대길이를 구하는 과정에서, 3번인덱스인 '5'의 값을 고르게 되면

   이 때, 5번 인덱스의 길이는 3번인덱스의 값 + 1 이된다.

   최대길이를 이런식으로 구할 수 있게 된다. 아래의 코드를 보면서 정리를 한번 해보자.

for (int i = 1; i <= N; i++)           // 1부터 N번 인덱스까지 반복한다.
    {
        DP[i] = 1;                 // 증가하는 부분수열의 최대길이의 초기값은 1
        for (int j = 1; j <= i; j++)    // 1. 이전에 있는 값들을 확인한다.
        {
            if (Arr[j] < Arr[i] && DP[i] < DP[j] + 1)    // 더 작은 값이면서, 해당 인덱스를 골랐을 때

            {                                        // 1증가한 크기가 기존의 값보다 크다면
                DP[i] = DP[j] + 1;                    // 해당 인덱스를 선택하고 크기 갱신
            }
        }

        if (Max < DP[i]) Max = DP[i];        // 최대 증가하는 부분수열의 크기값 저장

    }

3) 위에서 말한대로, 최대 증가하는 부분수열의 크기를 구했다고 가정하자. 그렇다면 우리는 무엇을 해야될까?

   우리가 가장 큰 증가하는 부분수열의 크기를 구한 이유는, 그 수열들을 기준점으로 삼고, 나머지 아이들을 옮겨주기만 하면

   답을 도출해 낼 수 있을 것이라 생각했기 때문이다. 즉, 전체 크기에서 최대 증가하는 부분수열의 크기만큼을 뺀 값이

   우리가 옮겨주어야 할 아이들의 수가 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 200 + 1
using namespace std;
 
int N, Max;
int Arr[MAX];
int DP[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
 
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (Arr[j] < Arr[i] && DP[i] < DP[j] + 1)
            {
                DP[i] = DP[j] + 1;
            }
        }
        if (Max < DP[i]) Max = DP[i];
    }
 
    cout << N - Max << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}