문제 풀이

[c++] 백준 7570 줄 세우기

미분당한 적분상수 2023. 5. 5. 04:37

 

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

 

7570번: 줄 세우기

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하

www.acmicpc.net

처음에 문제를 보았을 때, LIS(최장 증가 부분 수열)을 구하여 답을 구하는 문제인 줄 알았다.

 

하지만 LIS가 { 3, 5, 7 } 이라면 { 3, 5, 7 } 을 제외한 다른 것을 이동시켜도

번호순으로 줄 세우는 상황을 만들 수 없다.

 

따라서 번호순으로 줄 세우는 상황을 만들려면 연속적인 증가 부분 수열를 찾아야 한다.

 

LIS와는 다르게 연속적인 증가 부분 수열이라면 찾기 쉬워진다.

 

수열을 차례로 입력받으면서 입력받은 숫자가 만약 k라면 k-1이 전에 입력받은 적이 있는지 확인하고,

입력을 받은 적이 있으면 연속적인 증가 부분 수열의 길이에 1 더해준다.

 

이 과정을 이용해 연속적인 최장 증가 부분 수열의 길이를 구한다.

 

이 길이는 움직이지 않아도 되는 수의 개수이므로, 전체 수열의 길이에서 빼서 답을 구한다.

#include<bits/stdc++.h>
using namespace std;
int tmp[1000001];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    int ans=0;
    for(int i=0; i<n; i++){
        int k; cin>>k;
        tmp[k] = tmp[k-1]+1;
        ans = max(ans, tmp[k]);
    }
    cout << n-ans;
    return 0;
}