BOJ)2872 우리집엔 도서관이 있어

문제: icpc.me/2872

책의 순서가 주어졌을 때 책을 정렬하는데 필요한 최소 이동횟수를 출력하는 문제이다.

책을 이동하는 조건은 무조건 하나의 책을 들어서 맨위에 쌓는 방법밖에 없기 때문에

가장 뒤에 있어야 하는 책은 옮길 필요가 없다.

가장 큰 숫자부터 연속 된 숫자가 얼마나 긴 부분 증가 수열을 이루고 있는지 확인하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, a[300030], here;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    here = n;
    for (int i = n - 1; i >= 0; i--) 
        if (a[i] == here)here--;
    printf("%d\n", here);
    return 0;
}