(BOJ) 3653 영화 수집

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

사용 알고리즘: 세그먼트 트리

푸는 방법:

1. n+m 크기의 배열 만들어 영화들의 위치를 저장. 

   pos[m+n]부터 값을 넣는데 1이 가장 위로 가도록 한다.

   -> pos[m]=1, pos[m+1]=2, pos[m+2]=3 .........

   -> update() 함수 이용해서 해당 위치에 1 저장

2. 변수 t에 제일 위에 있는 영화의 인덱스 저장.

3. a번 영화를 뽑을 때

   - query() 함수 이용해서 t~pos[a]에 존재하는 영화의 개수 출력.

   - update() 함수 이용해서 pos[a]위치에 값이 0이 되게 하고,

       t--;   pos[a]=t;  해줌

   - 다시 update() 함수로 t위치의 값에 1 넣어줌 (a가 맨 위에 왔으니까)

   

   

소스 코드:

https://gist.github.com/hovy1994/7d9134b9a9122e553c39d28d5a7e5b01#file-3653