문제 풀이
[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;
}
