7570 줄 세우기

7570 줄 세우기 https://www.acmicpc.net/problem/7570

N명의 학생들이 N개의 서로다른 번호를 갖고있다.
학생을 맨앞으로, 맨뒤로 보내는 연산이 있을 때 번호순으로 정렬시키려면
최소로 몇번의 연산을 해야하는지 구하는 문제이다.

처음에 lis알고리즘으로 최장 부분수열을 구해서 N에서 빼주면 될거같았다.
제출하니까 틀렸다.
반례는 많았다.
{2, 5, 6, 4, 3, 1} - 답은4인데 3이나온다.

풀 수 있는 방법은 최대 부분 연속+1증가 수열을 찾는것이다.

#include <cstdio> #include <algorithm> using namespace std; int N; int arr[1000001]; int save[1000001]; int main() {     int cnt = 0;     scanf("%d", &N);     for (int n = 0;n < N;n++) scanf("%d", &arr[n]);     for (int n = 0;n < N;n++) {         cnt = max(cnt, save[arr[n]] = save[arr[n] - 1] + 1);     }     printf("%d\n", N - cnt);     return 0; } Colored by Color Scripter

cs

이런 방식을 생각해내기가 어렵다...