문제
https://www.acmicpc.net/problem/2872
문제해설
쌓아져있는 책을 정렬시켜야 한다.
아래쪽에 있는 책을 뽑아 가장 위에 올려놓을 수 있다.
이 경우에 가장 적게 책을 움직여서 정렬할 수 있는 횟수를 구하면 된다.
문제풀이
여러 경우를 직접 해보다보니 규칙을 알게되었다.
예를들어
4 5 3 6 2 1 이런 책들이 있다고하면
4 5 6 은 이미 정렬이 되어있고 3 2 1만 정렬해주면 된다.
그래서 옮겨야 하는 횟수는 3이다.
그럼 이 경우는 어떻게 될까
4 5 3 7 6 2 1 이 경우에는 7빼고 나머지 수들을 전부 옮겨야 하므로 7이 정답이다.
결국 이 문제는 가장 큰 수에서부터 위로 올라가며
가장 긴 증가수열을 찾아서 n에서 빼주면 된다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<int>arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i];
int cnt = n;
for (int i = n - 1; i >= 0; i--) {
if (arr[i] == cnt)
cnt--;
}
cout << cnt;
return 0;
}