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번으로 위치 갱신.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [3895] 그리고 하나가 남았다 (0) | 2023.03.24 |
|---|---|
| [3770] 대한민국 (0) | 2023.03.14 |
| [7578] 공장 (0) | 2023.03.11 |
| [1280] 나무 심기 (1) | 2023.03.09 |
| [1725] 히스토그램 (0) | 2023.03.07 |