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

우리집엔 도서관이 있어

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

1396

557

456

42.577%

문제

상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다.

오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다.

책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 수 있다. 가장 먼저, 2번 책을 뺀 다음에 가장 위에 놓는다. 그렇게 되면 (2, 3, 1)이 된다. 마지막으로, 1을 뺀 다음 가장 위에 놓으면 (1, 2, 3)이 된다.

현재 책이 어떻게 쌓여있는지가 주어졌을 때, 몇 번만에 사전 순으로 쌓을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 책의 개수 N이 주어진다. (N ≤ 300,000)

다음 N개 줄에는 가장 위에 있는 책부터 아래에 있는 책까지 순서대로 주어진다.

출력

첫째 줄에 몇 번만에 책을 정렬할 수 있는지 출력한다.

#include <iostream>
#include <vector>
int n;


using namespace std;
int main() {
    cin >> n;
    vector<int> v(n+1);
    for(int i=1; i<=n; i++){
        cin >> v[i];
    }
    int num =n;
    for(int i=n; i>0; i--){
        if(v[i] == num){
            num--;
        }
    }
    
    cout << num;
    return 0;
}

 

여기서 num은 옮겨야하는 수이다. 최대 n번(그 이상 움직일수는 있지만 의미 없다.)을 움직인다면 결국 어떤 배열이든 우리가 원하는 대로 정렬할 수 있다. 우리는 이러한 조건을 바탕으로 최대 움직일 수 있는 수 n에서 움직이지 않아도 되는 수를 뺄 것이다.

예를 들어 3 2 4 5 1의 경우 1부터 왼쪽으로 이동하며 비교해보면 3 4 5 이 세가지 수는 올바른 순으로 정렬되어있는것을 확인할 수 있다. 우리는 2를 뽑아 3의 앞으로 1을 뽑아 맨앞으로 총 2번만 옮기면 되는 것이다.

결국 총 5(n)번에서 올바른 순으로 정렬되어 움직일 필요없는 3을 빼면  움직여야하는 수는 2임을 알 수 있다