백준 2872 - 우리집엔 도서관이 있어 c

문제 링크

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

2872번: 우리집엔 도서관이 있어

풀이 아이디어

처음엔 어떻게 풀지 좀 막막하다가, 여러 그림을 그려보고 방법을 깨닫게 되었다.

다음과 같이 책이 놓여져 있다고 치자.

3

1

4

5

2

이 경우, 2를 먼저 맨위로 올리고, 1을 그 다음에 올리면 총 2번만에 책을 12345로 정렬할 수 있다.

그 말인 즉슨, 345는 정렬이 이미 되어있다는 뜻이다.

3

1

4

5

2

이렇게 3개의 책은 정렬이 되어있다는 뜻.

즉 아래에서부터 올라오면서 제일 큰 숫자를 기준으로, 1씩 증가되는 수열의 길이를 구한다음, 총 책의 갯수에서 빼면 된다.

 

코드

#include <cstdio>
using namespace std;
int n, b[300001], cur;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &b[i]);
    cur = n;
    for (int i = n - 1; i >= 0; i--)
        if (b[i] == cur)cur--;
    cout<<cur
    return 0;
}