티스토리 뷰

PS/BOJ

[BOJ] 백준 3653번: 영화 수집

박트리 2017. 3. 29. 21:11

영화 수집


문제


쿼리마다 i 번째 영화 위에 쌓여있는 다른 영화의 수를 출력하는 문제이다.



문제 풀이


naive하게 쿼리마다 현재 영화보다 위에 있는 영화를 카운트하는 방식으로는 \(O(NM)\) 이라 불가능하고, 힌트로는 영화를 꺼냈을 때 그 부분이 밀쳐지지 않고 비워진다는 방식으로 이해한다는 것이다. 그리고 영화를 꺼내면 맨 위에 차곡차곡 쌓는다. 그래서 현재 i층에 영화가 존재하는지, 안 하는지를 저장하는 \(check[i]\)을 생각해 보자.


 index

value 

 0

 0 

 1

 0

 2

 0

 ....

 ..

 m

 1

 m+1

 1

 m+2

 1

 ...

 ...

 m+n-1

 1


초기의 \(check[i]\)값은 위와 같다. 여기에 현재 i번째 영화가 어디 있는지에 대한 \(idx[i]\) 배열을 만들어 준다. 초기에는 \(idx[i]=m+i\)값이 들어가게 된다.

여기서 쿼리로 k번 째 영화를 찾는다면 \(\sum_{i=0}^{idx[k-1]} {check[i]}\) 값을 출력하고 \(check[idx[k]]\) 값을 0으로 그리고 맨 위에 해당하는 위치에 check[i]를 1로 바꿔주면 된다. 여기서 구간 합을 구하기 위해서 팬윅트리를 이용하면 된다.

\(O(MlgN)\)

 

소스 코드


'PS > BOJ' 카테고리의 다른 글

[BOJ] 백준 10875번: 뱀  (1) 2017.04.03
[BOJ] 백준 13460번: 째로탈출 2  (13) 2017.03.31
[BOJ] 백준 1941번: 소문난 칠공주  (2) 2017.03.27
[BOJ] 백준 10251번: 운전 면허 시험  (0) 2017.03.26
[BOJ] 백준 11509번: 풍선 맞추기  (0) 2017.03.26
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함