[백준]3653 영화 수집

K_Gs·2022년 4월 9일

BOJ

목록 보기

5/12

[정답이 아니라 풀이 기록입니다.]

DVD들에 연속적으로 번호가 붙은 채로 쌓여있다. DVD를 고르면 그 DVD를 뽑아서 맨 위로 올린다. 쿼리마다 보고 싶은 영화의 번호가 들어온다. 보고 싶은 영화 위에 쌓여있는 DVD의 개수를 출력하시오

접근

DVD의 수는 정해져 있습니다.
뽑을 영화의 개수도 정해져 있습니다.
DVD를 뽑아서 맨 위로 올리게 되면 뽑은 DVD의 바로 위 ~ 꼭대기 사이 DVD들의 '위에 쌓여있는 DVD 개수'가 변하게 됩니다.
1번 DVD가 맨 위에 있습니다.

구현

위에 쌓여있는 DVD

임의의 번호 A 위에 쌓여있는 DVD의 수는 A의 바로 위 ~ 꼭대기까지 있는 DVD의 수입니다.
즉, A의 바로 위 ~ 꼭대기 까지 있는 DVD의 수의 구간합입니다.
그리고 구간합은 세그먼트 트리로 익숙하게 구할 수 있습니다.

이 문제는 세그먼트 트리의 응용이고, 세그먼트 트리를 알고 있다는 가정하에 진행합니다.

확장

1~100의 DVD가 있을 때 이 DVD들의 위치는 역순인 100~1입니다.

[100][99][98][97]...[5][4][3][2][1] // 앞에서부터 1번 인덱스, 총 100개

이 상황에서 DVD 100번을 위로 올린다면?

[99][98][97]...[5][4][3][2][1][100] // 앞에서부터 1번 인덱스, 총 100개

DVD 100번의 인덱스를 100으로 바꿀 수 있습니다.
그런데 이렇게 하게 되면 나머지 인덱스들을 전부 한 칸씩 당겨야 합니다.
세그트리에서 값을 바꾸는 연산은 O(log n)이고 이걸 다 바꿔야 하니 O(nlogn)입니다.
쿼리마다 하기에는 시간 부분에서 조금 비효율적인 것 같네요. 굳이 당겨야 할까요?

[0][99][98][97]...[5][4][3][2][1][100] // 앞에서부터 1번 인덱스, 총 101개

그냥 기존위치를 비우고 뒤에 다른 인덱스에 추가하면 될 것 같네요!
공간적으로는 손해이지만 당기면서 소모되는 시간을 아낄 수 있게 되었습니다.

이렇게 한다면 쿼리마다 무조건 한 칸 뒤로 인덱스가 늘어나고 그렇기에 최대 (DVD의 수 + 쿼리의 수)만큼 인덱스를 사용합니다. 이 최대 인덱스만큼 트리를 만들어두면 (DVD의 위치~확장된 인덱스)를 통해 구간합을 구할 수 있습니다.

트리를 (1,n)구간이 아닌 (1,n+m)구간으로 구현

요약하자면 위와 같습니다.

한편 DVD 번호로 쿼리가 들어오기에 그 번호의 DVD가 현재 어디에 저장되어있는지 알아야 (DVD의 위치~확장된 인덱스)로 쿼리를 돌릴 수 있기에 loc배열을 만들어 기록해 둡니다.

처음 loc[i] = N-i+1

구간합 구하기

위에선 트리의 인덱스 확장을 보기 위해 DVD의 번호를 넣었지만, 실질적인 DVD의 위치는 loc에서 관리하기에 세그먼트 트리에는 그 인덱스에 DVD가 들어있는지 없는지만 저장하면 됩니다.

1 -> 들어 있다
0 -> 안 들어 있다.

임의의 A가 쿼리로 들어오면 A의 인덱스는 loc[A]에 저장되어 있습니다.
그리고 A 위에 있는 DVD의 수이기에 (loc[A]+1,현재 확장된 인덱스)구간으로 구간합을 구하고 출력합니다.

이후 loc[A]위치의 A번 DVD를 맨위로 올렸기에 트리에서 loc[A]위치로 들어가 0으로 update합니다.
그리고 (현재 확장된 인덱스+1)로 가서 1로 update합니다.
다음으로 loc[A] = 새로 들어간 인덱스로 저장합니다.

for (int i = 1; i <= m; i++) {
			scanf("%d",&a);
			printf("%d ",sum(1, n + m,1,loc[a]+1,Count));//구간합
			update(1,n+m,1,loc[A],0);//기존 위치에서 DVD 제거
            update(1,n+m,1,++Count,1);//새 위치에 DVD 추가
			loc[a] = Count;//위치 업데이트
}