BOJ 3117 Youtube

이 문제는 LCA를 O(logN)만에 구할 때 쓰는 방법(dp이용)과 비슷하다.

m이 너무 크다는 것이 문제인데, 예를 들어 동영상A의 2의 k제곱번째 뒤 동영상은 동영상A의 2의 (k-1)제곱번째 뒤 동영상의 2의 (k-1)제곱번째 뒤 동영상과 같다는 사실을 이용하면
O(logM)만에 구할 수 있다.

그리고 어떤 수든 이진법으로 나타내보면 2의 k제곱들의 합으로 표현할 수 있다는 것을 알 수 있는데, 즉 (m-1)값을 2의 k제곱들의 합으로 보면서 2의 0제곱, 2의 1제곱, ... 2의 k제곱..이렇게 logM만큼만 뛰어 넘으면 m번째 동영상에 도달할 수 있다.

이분탐색과 비슷한 느낌이기도 하고...
 LCA처럼 미리 전처리를 하는 방법도 있고(나는 이렇게 했다.) 다른 사람의 코드를 보니 그냥 바로바로 계산할 수 있는 방법도 있다.

바로 바로 계산하는 방법은 처음에 2의 0제곱번째 뒤 동영상 정보만 가지고 있는 배열을 이용해서 계산을 시작하고, 2의 0제곱번째 뒤 정보의 배열을 이용해서 2의 1제곱번째 뒤 정보의 배열을 만들고, 그것을 이용해서 2의 2제곱번째 뒤 정보를 가진 배열을 얻고(덮어 씌우고).. 이런 식으로 나아가면 적은 메모리로도 똑같이 계산할 수 있다.