[ 2872 ] 우리집엔 도서관이 있어

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

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

 

---

풀이 과정

---

1. 맨 오른쪽에서부터 왼쪽으로 진행하면서 N을 찾는다.
2. N이 아니라면 옮겨야 되는 값이므로 횟수를 하나 증가시킨다.
3. N이라면 찾아야 하는 값을 N-1로 줄여서 현재 위치에서부터 찾는다.
4. 2-3을 맨 왼쪽까지 반복한다.

- 위 과정을 반복하면 찾아야 하는 값 기준으로 왼쪽에서 보았을 때 증가하는 수열이 나온다.(맨 마지막 값이 N)

- 또한, 옮겨야 되는 값들은 큰것부터 작은것 순으로 맞추어서 앞에 넣어주기만 하면 되기 때문에 결국 (2)에서 구한 횟수를 그대로 리턴해주면 된다. 

- 생각보다 잘 안풀리는 문제였음

 

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
books = [int(input()) for _ in range(N)]

find_target = N
answer = 0
for i in range(N-1, -1, -1):
    if books[i] != find_target:
        answer += 1
    else:
        find_target -= 1

print(answer)