백준 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 분 후 동영상.

	#include <bits/stdc++.h>
	using namespace std;
	// LCA 에서 쓰는 방식
	const int MAX = 100001;
	int N, K, M, student[MAX];
	int video[MAX][32];
	int MakeAns(int curr, int Remain){
	int idx = 0;
	while(Remain){
	if(Remain%2) curr = video[curr][idx];
	idx++;
	Remain/=2;
	}
	return curr;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> K >> M;
	for (int i = 1; i <= N; ++i)
	cin >> student[i];
	memset(video,-1,sizeof(video));
	for (int i = 1; i <= K; ++i) cin >> video[i][0];
	// video[i][j] = i동영상 에서 2^j 번만큼 갔을 때 동영상
	for (int j = 0; j < 31; ++j){
	for (int i = 1; i <= K; ++i){
	int parent = video[i][j];
	video[i][j+1] = video[parent][j];
	}
	}
	for (int i = 1; i <= N; ++i)
	cout << MakeAns(student[i],M-1) << ' ';
	return 0;
	}

view raw BOJ 3117.cpp hosted with ❤ by GitHub