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

www.acmicpc.net/problem/2872

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

---

풀이

정렬문제인줄 알고 한참 헤맸다.

 

또한 문제에서 요구하는대로 그대로 구현하니 시간초과가 떳다.

 

법칙을 찾아야한다.

 

45123 순서로 책이 들어온다고 하면, 45는 그대로 두고 123을 위로 올려야 할것이다.

3 2 1 순으로 뽑아야 겠지만 순서는 중요하지 않다. 책을 뽑는 횟수를 세는것이기 때문에 3개라는게 중요하다.

 

12453 이면 어떨까? 이것도 45만 남겨두고 나머지를 다 위로 올리는 작업을 해야한다.

 

즉 최대숫자인 5를 찾고 왼쪽으로 바로 감소하는 수(4)를 제외하고는 모두 뽑는 작업을 거쳐야한다.

 

21345라면 2345 는 5부터 연속으로 감소하기 때문에 뽑지 않는다. 하지만 3에서 1로는 연속으로 감소하지 않는다.

 

답은 N - 연속으로 감소하는 개수 이다.

 

---

코드

import sys
input =sys.stdin.readline

N = int(input())
arr = [int(input()) for i in range(N)]
max_num = max(arr)
max_idx = arr.index(max_num)
target = max_num-1
cnt=0
for i in range(max_idx,-1,-1):
    if arr[i] == target:
        cnt+=1
        target-=1
print(N-1-cnt)