백준 2872번[c/c++] : 우리집엔 도서관이 있어

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

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

---

풀이

• 첫째 줄에 책의 개수 N을 입력한다.
• 예시를 보면 제일 큰 숫자 4는 -> 3과 4로 정렬이 되어있다.  즉 2를 위로 옮기고 1을 옮기면 된다 (총 두번)

• 3, 2 ,4, 5, 1을 생각해보자.   3과 4와 5는 이미 3,4,5 순으로 정렬이 되어 있다. 그러므로 2를 맨 위로 옮기고 그 다음 1을 맨 위로 옮기면 된다. 총 두번을 옮기면 된다.
• 여기서 공식을 알 수 있다. 이미 정렬되어 있는 것들은 옮길 필요가 없다. 정렬되어있지 않은 것들만 옮기면 된다.   정렬되지 않은 것들을 알 수 있는 방법은 간단하다. 배열의 맨 마지막값에서 부터 맨처음 값을 비교하면 된다.     배열의 마지막 부터 처음까지 값을 조사하는데 값이 n가 같으면 정답은 n-1이 된다. 그 다음 배열의 값이 또 n-1가   같다면 정답은 (n-1)-1이 된다(이미 정렬된 것들을 빼는 원리임)

#include<stdio.h>

int main() {
	int n;
	int book[300001];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &book[i]);
	int answer = n;
	for (int i = n - 1; i >= 0; i--)
		if (book[i] == n)
			answer--;
	printf("%d", answer);
	return 0;

}

#include<iostream>
#include<vector>

using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> book(n);
	for (int i = 0; i < n; i++)
		cin >> book[i];

	int answer = n;
	for (int i = n - 1; i >= 0; i--)
		if (book[i] == answer)
			answer--;
	cout << answer;
	return 0;
}