백준 3653번 영화 수집 - 스위프트(Swift) 풀이 + 그림 설명

 CLASS 6에 펜윅트리로 풀 수 있는 문제가 또 남아있길래ㅎㅎ 이제 1 문제만 더 풀면 CLASS 6 딸 수 있다!!

 먼저 DVD가 쌓여있는 상황을 어떻게 표현할지부터 생각해야 한다. 간단하게 아래로 갈수록 항상 숫자(index)가 커지도록 매기는 방법을 떠올렸다. 이렇게 되면 x번 DVD를 뽑을 때 위에 놓인 DVD의 수는 index[x]보다 작은 index의 개수가 된다! 따라서 isIndexExist[i] = index 중 i라는 수가 존재하는가로 두면, index[x]보다 작은 index의 개수는 isIndexExist[1...(x-1)]의 구간합이 된다.

 

 만약 3번 DVD를 뽑아야 하는 차례이면, 먼저 3번 DVD의 위치(index)를 확인한다. index[3]은 3이다. 3보다 작은 index는 1과 2가 있으므로 3번 DVD 위에 쌓인 DVD 개수는 2개임을 알 수 있다. 이제 3번 DVD를 뽑아서 제일 위로 얹어야 한다. 아래로 갈수록 항상 숫자(index)가 커지도록 유지하기로 했으므로, 현재 가장 위에 있는 1보다 더 작게 0으로 주면 된다. 그 다음에 또 위에 얹을 차례에는 -1, -2,,, 이렇게 계속 작아지도록만 하면 된다.

 

 그런데 펜윅트리에서 인덱스를 음수로 줄 수 없으므로 양수가 되도록 한번 보정을 하자. DVD개수가 최대 100,000개이므로 index 값이 -99,999까지 갈 수 있다. 따라서 100,000씩 더해서 관리해주면 된다.