🤔 왜 떠올리지 못했을까?
우선 영화 수집 문제를 세그먼트 트리를 이용해 만들어야 하는 것을 알고 문제풀이를 시작했다. 세그먼트 트리를 이용하려고 보니... 이게 왠걸 이게 세그먼트 트리 문제인가도 헷갈릴 정도였다.
이 문제를 풀면서 세그먼트 트리를 활용해야 할 때는 대놓고 "나 세그먼트 트리요." 하지 않는 다는 것을 많이 느꼈다. 또한 전에 다른 문제들을 풀면서 활용했던 확장 하는 개념을 떠올리지 못했기 때문에 자꾸만 헛돌게 되었다.
만약 비디오가 3개고 볼 영화가 4개 라면 [1, 1, 0, 0, 0, 0, 0] 이런 식으로 생상해 준 뒤에 빼야하는 비디오의 인덱스+1 부터 (N+M+1)까지 더한 값을 반환하면 된다.
본 영화의 값은 다음 인덱스 값으로 옮겨 준다. 만약 3번 영화를 봤다면 [0, 1, 0, 1, 0, 0, 0]로 바꾸어 준다. 사실 여기까지 아이디어 떠올리기도 어려웠지만, 바뀐 인덱스를 어떻게 관리할지도 헷갈렸다.
그래도 딕셔너리 형태를 이용해서 바로 관리 할 수 있었다.
또한 이것들의 합을 빨리 구하고, 업데이트를 빨리 했어야 했기 때문에 세그먼트 트리를 이용했어야 했다.
다른 분들의 풀이를 보니, 많은 분들이 비트마스킹을 이용해서 빠르게 푸셨더라, 다음에 다시 풀어볼 때는 나도 비트마스킹을 적용해서 최적화를 해야겠다.
문제 링크
https://www.acmicpc.net/problem/3653
내 풀이 링크
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_3653.py
