백준 3117번 Youtube

< 백준 3117번 Youtube - 마포 코딩박 >

사용한 알고리즘: ...?


 각 동영상들에 대해 다음 시청할 동영상이 각각 주어지고, 각 학생들이 처음 시청하는 동영상이 입력으로 주어집니다. 이때 M분이 지났을 때 시청한 동영상을 구하는 문제였습니다.
i 동영상에서 2^j 분 후 시청할 동영상을 video[i][j] 로 저장하고, M 을 2진수로 생각하여 해당 M분 후 시청할 동영상을 구하였습니다.

문제풀이는 다음과 같습니다.

(1) video[i][j] : i 동영상에서 2^j 분 후 시청할 동영상으로 생각합니다.

(2) video[i][0] 는 i 동영상 직후 (2^0 = 1) 시청할 동영상입니다. 이를 입력받습니다.

(3) video[i][j] = k 라 했을 때, video[i][j+1] = video[k][j] 입니다.
    예를들어 i 동영상에서 2^5 분후 시청하게된 동영상이 k 라 하면, i 동영상에서 2^6 분      후  시청하게 될 동영상 = k 동영상에서 2^5 분 후 시청하게 될 동영상 입니다.
   ( 코드 24 ~ 29 줄 )

(4) 각 학생이 처음 시청하는 동영상에서 M 분 후 동영상을 계산해 줍니다. M 을 2진수로 생각하여 계산해주면 됩니다.

   예를 들어, 처음 시청 동영상이 a1 이고 M = 13 일 경우, 13 = 2^3 + 2^2 + 2^0 이므로,
   a1 -> ( 2^0 분 후 ) a2 - > ( 2^2 분 후 ) a3 -> ( 2^3 분 후 ) a4
   a4 = a1에서 2^0 + 2^2 + 2^3 분 후 동영상.