[백준 7570] 줄세우기

[백준 7570] 줄세우기

문제 링크

int N;
int numbers[1000004];
int dp[1000004];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N;

    int ret = 0;
    int num;
    for(int i=1; i<=N; i++) {
        cin >> num;
        dp[num] = dp[num - 1] + 1;
        ret = max(dp[num], ret);
    }

    cout << N - ret << endl;

    return 0;
}

• LIS 응용 문제이다.
• 2631의 줄 세우기와 비슷하지만, 아이들을 정렬 할 때에 앞이나 뒤로만 보낼 수 있다는 것이 차이점이다.
• 그렇기 때문에 오름차순이면서, 크기가 1 차이만 나는 애들을 고정시키면 된다.