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

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

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

 

이미 정렬되어 있는 숫자가 몇개인지를 알아야한다.

예를들어 input이 다음과 같다면

1 3 4 2

이미 정렬되어 있는 숫자는 3,4이다. 

이유는 가장 큰 수는 4고 위로 올라가면서 4보다 1작은 3이 있다. 3보다 1 작은 2는 3위에 존재하지 않는다.

 

다른 예로 input이 다음과 같다면

3 1 4 5 2

이미 정렬되어 있는 숫자는 3,4,5다. 

가장 큰 수는 5고 위로 올라가면서 4를 찾고, 올라가면서 또 4보다 1 작은 3을 찾을수 있다.

따라서 이미 정렬되어 있는 3,4,5를 뺀 나머지 숫자들을 큰 수부터 맨위로 올려주면 된다.

 

즉 답은 n - 이미 정렬되어 있는 숫자의 갯수다

 

 

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> v;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    int target = n;
    int cnt = 0;
    for(int i = n-1; i >= 0; i--)
    {
        if(v[i] == target)
        {
            cnt++;
            target--;
        }
    }
    cout << n-cnt;
}