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

https://www.acmicpc.net/problem/2631

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 987654321
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr(n);
    //dp[i]: i번째 사람 까지의 LIS
    vector<int> dp(n, 0);

    for (auto &item: arr) {
        cin >> item;
    }


    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int ans = 0;

    for (const auto &item: dp) {
        ans = max(ans, item);
    }

    cout << n - ans;

    return 0;
}

1. 문제

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

입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

2. 풀이

 

 예제를 풀이하는 방법이다. 이동시킬 아이들의 수는 이미 순서대로 서 있는 아이들을 고정시키고 그렇지 않은 아이들의 위치를 이동시키는 것이 최솟값이다. 밑줄 친 증가 부분수열을 고정시켜두고, 적절하지 않은 자리에 있는 아이를 옮겨준다. 즉, 최장 증가 부분수열(LIS)를 구해 총 아이 수에서 빼주면 된다.

    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

• dp[i]: i번째 아이까지의 LIS

j번째 아이보다 i번째 아이의 키가 더 크다면 j번째 아이->i번째 아이로 증가 부분수열을 만들 수 있다. 최장 수열을 구하는 것이므로 i보다 앞에 있는 각 아이들에 대해 수열의 길이를 갱신해준다. 

    int ans = 0;

    for (const auto &item: dp) {
        ans = max(ans, item);
    }

    cout << n - ans;

전체 dp 중 최댓값을 구한다. dp의 인덱스가 높다고 반드시 그 길이가 길진 않으므로 모든 dp에 대해 구해주어야 한다. 이 문제의 목표는 아이를 옮기는 최소 수를 구하는 것이므로 LIS의 길이를 전체 학생 수에서 빼준다.