전체 글

백준 3653번 - 영화 수집

https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Point) DVD의 번호를 기준으로 세그먼트 트리를 만들면 로직이 꼬이기때문에 DVD 컬렉션상의 특정 위치의 DVD의 존재 유무를 기준으로 잡는 것이 좋다. DVD 하나를 빼서 맨 위로 올리는 것을 '액션'이라고 하자. 트리의 원본배열의 크기(구간합이 ..