BOJ 3653 영화 수집
알고리즘 문제풀이/BOJ
2019. 7. 30. 03:48
문제 출처 : ICPC NWERC Regional 2011 C https://www.acmicpc.net/problem/3653 백준에서 문제 풀다가 세그먼트 트리를 어떻게 활용할 수 있는지 보여주는 좋은 예시가 된 것 같아서 첫 개별 문제 포스팅을 정했다. 요점은, $n$개의 영화가 있고, 이게 순서대로 잘 꽃혀 있는데, 중간 뭔가를 빼서 보고 나면 맨 위에 놓는다. 이 행동을 $m$번 하는데, 매번 영화를 고를 때마다 위에서부터 몇 번째에 있는지를 확인하면 된다. 예를 들어, 1 2 3 4 5 순서로 정렬되어 있는데 여기서 4번을 빼고 나면, 4 1 2 3 5 로 바뀐다. 이때, 4번 위에는 원래 3개가 있었다. 이때, 2번을 꺼내면, 2번 위에 원래 2개가 있었고, 2 4 1 3 5 로 바뀐다. 볼..