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

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net

초기 세팅:

 

각 DVD에 대하여 해당 DVD가 쌓여지는 순서를 map에 저장

 

예를 들어, n = 100000일 때, 100000번 DVD는 젤 처음으로 쌓이고, 1번 DVD는 맨 마지막(100000번째)에, 2번 DVD는 99999번째로 쌓이기 때문에

map[100000] = 1, map[1] = 100000, map[2] = 99999

 

따라서, 초기 세팅 이후에 처음으로 i번 DVD가 뽑힌다면, map[i] = 100001이 되고, 그 다음으로 j번 DVD가 뽑힌다면, map[j] = 100002가 됨.

 

이런 식으로 update을 해주다보면, 임의의 DVD 배열 상태에서 map[DVD]의 value는 내림차순이 됨(배열을 위에서부터 아래로 훑을 때). 매 update마다 가장 최근에 뽑힌 DVD가 배열 상에서 가장 위로 올라가고, map[가장최근DVD번호]가 직전 배열에서 가장 큰 value값 + 1이기 때문. 즉, map의 value들은 정렬된 상태를 유지.

 

풀이:

 

DVD들을 map[DVD]의 value에 따라 C++의 set같은 이진탐색트리에 저장한다면, i번 DVD를 뽑아서 맨위로 올릴 때

1. map[i]의 value를 이진탐색트리에서 찾는다 → log(n)

2. map[i]보다 큰 value들의 개수를 구한다 → log(n)

3. value들은 오름차순을 유지하기 때문에 map[i]보다 큰 value들의 개수가 i번 DVD를 뽑을 때 i번 DVD위에 있는 DVD들의 개수.

 

이런 식으로 풀면 mlog(n)에 풀이가 가능하지 않나?