문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

실제 DVD를 중간에서 빼내 위에 올려놓는 것처럼 구현하기 위해서는, DVD를 찾는 것부터, 위에 있는 것들을 한 칸씩 내리는 것까지, naive하게 풀면 O(mn)이다. 보다 나은 알고리즘을 떠올려야 한다.

Algorithm

Segment Tree(Sum of Given Range)를 이용하면, 특정 구간의 값들을 갱신할 수 있고, 위 구간의 합도 쉽게 계산할 수 있다. 이때, 그냥 n 개의 elements를 대상으로 하는 Segment Tree를 사용하면, 의도한 대로 해결할 수 없다. m + n 개를 다룰 ST를 생성하고, DVD를 쌓아올릴 때, m구간에 차곡차곡 쌓아올리는 방식으로 해결해야 한다.

Data Structure

• Segment Tree
• 각 DVD의 position(0 ~ n+m-1)을 저장할 size n Array

결과

Other