https://www.acmicpc.net/problem/3653
3653번: 영화 수집
각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD
www.acmicpc.net
값을 삭제하고 앞에 삽입하는 걸 시간 내에 잘 해결해야 한다.
m+n짜리 0/1 배열이 있다고 생각하면 문제를 쉽게 해결할 수 있다.
처음에는 i번째 영화를 m+i번째 자리에 놓아 값을 1으로 둔다.
그 영화를 k번째로 고르면 영화를 맨 앞으로 옮기는데, 원래 위치의 값을 0으로 바꾸고 m-k를 1로 바꾸면 된다. 이렇게 하면 문제에서 요구하는 순서를 가지게 됨을 알 수 있다.
각각의 쿼리에서 요구되는 값은 해당 0/1배열에서 처음부터 주어진 영화의 위치까지의 합이다. 이 합을 세그나 펜윅으로 관리하면 된다.
각 영화의 위치에 접근하는걸 O(1)에 하도록 인덱스 배열을 만들어 관리하면 시간 내에 쿼리를 처리할 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 10265 MT (0) | 2023.01.26 |
|---|---|
| 백준 9376 탈옥 (0) | 2023.01.24 |
| 백준 3090 차이를 최소로 (0) | 2023.01.05 |
| 백준 7469 K번째 수 (0) | 2023.01.05 |
| 백준 15972 물탱크 (0) | 2023.01.05 |
