[DP]백준2631번 줄세우기

백준2631 줄세우기

이 문제는 LIS(최장 증가 수열) 알고리즘을 이용하여 풀 수 있는 문제다.

나는 이 방법을 떠올리지 못해 한참을 고민했다.

LIS는 주어진 수열에서 증가하는 최대 길이의 수열을 찾는 알고리즘이다.

이 알고리즘은 DP로 구현되며, 현재의 인덱스보다 작은 수들을 세는 방법과 비슷하다.

백준의 LIS 문제에 대해서는 백준11053 가장 긴 증가하는 부분수열 를 참고하면 된다.

최장 증가 수열 알고리즘의 풀이 방법을 이해하기 위해 가장 좋은 설명은

“자신보다 작은 애들을 찾고, 그 작은 애들 중에 자기보다 작은게 제일 많았던 애의 값 + 1을 자신의 값으로 취하는 것.” 정도가 될 것 같다.

줄 서 있는 아이들 수열에서 최장 증가 수열을 찾는다.

3 7 5 2 6 1 4

에서 최장 증가 수열은 3, 5 ,6 으로 길이 3이다.

문제에서 예시로 든 이동하는 아이들은 4, 7, 1, 2 이다.

즉, 최장 증가 수열에 속하지 않는 아이들이 움직인다.

수열에서 최장 증가 수열을 찾았다는 것은, 찾은 수열이 전체 수열 내에서 가장 큰 증가하는 수열이라는 뜻이다.

따라서 해당 최장 증가 수열을 뼈대로 두고 나머지 아이들을 이동시켜 정렬하는 것이 최소로 아이들을 움직이는 경우이다.

#include <iostream>

using namespace std;

int arr[205];
int dp[205];

int main(){
    int N;
    cin >> N;
    
    
    for(int i=1;i<=N;i++){
        cin >> arr[i];
        dp[i] = 1;
    }
    // LIS
    dp[1] = 1;
    for(int i=2;i<=N;i++){
        int tmp = 0;
        for(int j=1;j<i;j++){
            if(arr[j] < arr[i] ){
                if(dp[j] > tmp){
                    tmp = dp[j];
                }
            }
        }
        dp[i] = tmp + 1;
    }
    int answer = 0;
    for(int i=1;i<=N;i++){
        if(dp[i] > answer )answer = dp[i];
    }
    cout << N - answer;
    return 0;
}