https://www.acmicpc.net/problem/3653
3653: 영화집
각 테스트 케이스에 대해 한 줄에 m개의 정수를 출력해야 합니다.
i번째로 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있던 DVD의 수이다.
상근은 매번 영화를 볼 때마다 본 영화 DVD
www.acmicpc.net
세그먼트 트리 문제이다.
접근법은 떠오르지 않는다.
다른 사람들의 수영장보고 나서 풀었다.
풀
n개의 DVD 중 임의의 DVD를 m회 선택하고 나서 시청한 후, 맨 위에 놓는다는 이야기는 세그먼트 트리의 입장에서 n개의 DVD 앞에 m개의 빈 스페이스가 필요하다고 하는 이야기 된다.
리프 노드 m + n 개를 표현할 수있는 구간 합 세그먼트 트리를 생성한다.
마지막으로 n개의 구간(m~m+n)에 하나씩 추가하여 첫 번째 상태의 DVD 위치를 지정합니다.
X번 DVD가 선택되면(0~X-1) 구간의 구간합을 돌려, 해당 DVD를 m-0번 구간으로 이동하고, 다음 선택된 DVD는 m-1번 구간으로 이동하면서 반복하면 된다.
예제를 기반으로 다음과 같이 그래프 상태를 그릴 수 있습니다.
초기 상태의 트리와 배열의 모습이다.
배열에는, 1번부터 3번의 DVD가 트리의 어느 구간에 있는지를 나타낸다.
최초로 3번 DVD의 경우는 5번에 위치. 즉, 0~4번까지의 구간합을 출력한다.
그 후 자신의 위치를 DVD 진열의 최상단인 2번 인덱스로 이동. 이후 3번 DVD의 위치를 갱신해 준다.
다음에, 1번 DVD의 위치는 3번이므로, 0~2번 구간 합을 출력한다.
그 후 해당 DVD는 다음 최상단 인덱스인 1번으로 이동.
1번 DVD를 확인. 이번에는 0~0 구간의 구간화를 출력하면 된다.
마지막 위치인 0번에 위치 갱신.
정답 코드
