백준 3653번 영화 수집

문제링크: https://www.acmicpc.net/problem/3653

사용한 알고리즘: 펜윅 트리


N개의 영화가 1~N 순으로 쌓여있고(초기 1번 영화가 맨위), i번째 영화를 볼때마다 해당 위치에서 맨위로 순서를 옮기는 문제였습니다. 저는 펜윅트리를 이용해 문제를 풀었습니다.
문제의 요점은 본인 앞에 몇개의 영화가 있느냐였습니다.

문제풀이는 다음과 같습니다.
(1) 펜윅트리의 1~MAX(=1111) 까지를 먼저 비워놓는다고 생각했습니다. 즉, 처음 영화를 입력 받을때 i 번째 영화는 MAX+i 번째에 위치 시켰습니다. 이때 새로운 배열을 하나 만들어 영화 위치를 저장해주었습니다.

(2) 이후 k번째로 영화를 고르면, 저장해둔 해당 영화의 위치(h)를 MAX-k에 위치 시키고, h뒤에 -1을 더해주었습니다. (애초에 해당 영화 밑에 쌓여있던 영화들의 순위는 변함없어야 합니다.) 처음 시작시 1~MAX까지 자리를 비워뒀기 때문에 해당영화 앞에는 영화가 없게 됩니다.