[백준 2631] 줄세우기

[백준 2631] 줄세우기

문제 링크

using namespace std;
int N;
int numbers[1000004];
int dp[1000004];
int main() {

    cin >> N;

    for(int i=0; i<N; i++) cin >> numbers[i];

    int ret = 0;
    for(int i=0; i<N; i++) {
        dp[i] = 1;
        for(int j=0; j<i; j++) {
            if(numbers[i] > numbers[j] && dp[j] + 1 > dp[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ret = max(ret, dp[i]);
    }
    cout << N - ret << endl;

    return 0;
}

• LIS 응용 문제이다.
• 아이들을 오름차순으로 순서대로 정렬하기 위한 최소 움직임을 구하는 문제이다.
• 움직이는 데에 제약은 없기 때문에, 이미 자리를 찾은 아이는 두고, 잘못 있는 애들만 옮겨주면 된다.
• 그렇다면 오름차순으로 정렬 되어 있는 가장 긴 배열의 길이를 찾으면 된다. -> LIS
• 전체 길이에서 LIS의 길이를 빼면 된다.