알고리즘 (PS)/BOJ
[백준] 3653 - 영화수집 (P4)
https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 세그먼트 트리 연습 문제로 풀게 된 문제 1시간을 고민해도 아이디어가 전혀 안 떠올라서 블로그 3~4개 풀이를 다 읽어보고 겨우 이해했다. 그리고 구현하는데 또 시간초과 나서 구현 디테일 수정하느라 30분은 또 쓴 것 같다. 영화를 볼 때마다 꺼낸 영화보다 위에 있던 영화들의 위치가 한칸씩 밀리는 것이 이 문제의 어려운 점이다. 이는 N+M개의 리프노드를 가지는 세그트리를 구현하여 해결할 ..
