BOJ 3117 YouTube

문제

• 링크 - https://www.acmicpc.net/problem/3117

문제 분류

• 난이도 - 중
• 태그 - 동적계획법

문제 풀이

경험이 없으면 풀기 까다로운 문제다. 단순하게 동영상을 순회하면서 풀고자 하면 당연히 시간초과가 발생한다. 동적계획법을 생각해봐도 \(M\)이 10억이라 딱히 감이 오지 않는다. 그런데 다음과 같은 점화식을 세울 수 있으면 문제가 해결된다.

dp[i][j] = i 번 동영상에서 \(2^j\) 분 후, 시청할 동영상

dp[i][j] = dp[ dp[i][j-1] ][j-1]

위의 점화식을 간단하게 설명하면 a번 동영상에서 2x분 후에 시청할 동영상은 a번 동영상에서 x분 후에 시청할 동영상 b를 구한 뒤, 다시 b번 동영상에서 x분 후에 시청할 동영상 c를 구하면 된다는 것이다. 단순하게 1, 2, 3,... 분 후에 시청할 동영상을 계산하는 것이 아니라 \(2^0, 2^1, 2^2, ...\) 분 후에 시청할 동영상을 계산한다는 것이 중요하다. 이것을 가지고, \(M\) 분 후 동영상을 적절히 맞춰가면 된다.

소스 코드

#include <bits/stdc++.h> using namespace std; const int MAX_K = 1e5; int n, m, k; int dp[MAX_K + 1][31]; int main() { scanf("%d%d%d", &n, &k, &m); vector<int> movie(n); for (int i = 0; i < n; i++) { scanf("%d", &movie[i]); } for (int i = 1; i <= k; i++) { scanf("%d", &dp[i][0]); // i번 동영상의 바로 다음 동영상(1분 뒤) } for (int i = 1; i < 31; i++) { for (int j = 1; j <= k; j++) { dp[j][i] = dp[dp[j][i - 1]][i - 1]; } } for (int i = 0; i < n; i++) { int jump = m - 1; int no = movie[i]; // m-1 분을 2의 거듭제곱들로 채우면 된다. for (int j = 0; j < 31; j++) { if (jump & (1 << j)) { no = dp[no][j]; } } printf("%d ", no); } }