백준 2631번: 줄세우기

백준 2631번: 줄세우기

2631번: 줄세우기

문제를 풀다보면 풀지못하는 문제도 있는 법인데 나중에 확인해보니 초등부, 중등부 문제인 것을 알았을 때, 나는 얼마나 걸음마 단계인지 실감하게된다. 이 문제도 풀지못하고 답을 봤는데 예전에 풀었던 가장 긴 증가하는 부분수열과 풀이 방법이 똑같다는 것을 알았다. 배운것도 못써먹었다는 것에 좌절감을 느꼈다. dp문제를 풀지 못한 결정적인 이유는 아무래도 규칙을 못찾은 것이 아무래도 큰 요인이라고 볼 수 있겠다.

 

가장 긴 증가하는 부분수열 문제를 풀 때 LIS 알고리즘이란 것을 사용했다. 배열 그보다 작은 수들을 체크해가며 dp가 큰 값들에서 +1을 하는 것이다. 줄세우기에도 똑같은 방법을 사용했는데 문제가 말이 엄청 복잡하게 되어있지만 결국 풀이해보면 제대로 서 있는 친구들은 가만히두고, 뒤죽박죽 섞여있는 친구들만 원래 위치로 옮기면 되는 것이다.

예제를 들어보자

3 7 5 2 6 1 4

이런 순으로 줄을 서 있다면

3 7 5 2 6 1 4

가장 큰 증가하는 부분수열인 3 5 6만 남기고 나머지를 원래 위치로 옮기기만하면 된다.

따라서 전체 인원 - 가장긴 부분수열 크기 = 아이들이 이동하는 횟수가 되는 것이다.

 

// LIS 문제

#include <iostream>
using namespace std;

int dp[201];
int child[201];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int res = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> child[i];
    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = 0; j < i; j++){
            if(child[i] > child[j]){
                t = max(t, dp[j]);
            }
        }
        dp[i]=t+1;
        res = max(res, dp[i]);
    }
    cout << n - res;
    
    return 0;
}