[BOJ 3117 // C++] YouTube

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3117번 문제인 YouTube이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3117 

3117번: YouTube

sparse table 자료구조를 이용해 영상을 \(2^0, 2^1, 2^2, ..., 2^{29}\)분동안 본 뒤에 보고 있을 영상이 무엇인지를 미리 구해두고, 주어지는 M의 이진표현을 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int N, K, M;
int table[100001][30];
int Q[100001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K >> M; M--;
	for (int i = 0; i < N; i++) cin >> Q[i];

	for (int i = 1; i <= K; i++) {
		int nxt; cin >> nxt;
		table[i][0] = nxt;
	}

	for (int k = 1; k < 30; k++) {
		for (int i = 1; i <= K; i++) {
			table[i][k] = table[table[i][k - 1]][k - 1];
		}
	}

	for (int i = 0; i < N; i++) {
		int& cur = Q[i], m = M;
		for (int i = 0; i < 30; i++) {
			if (m & 1) cur = table[cur][i];
			m >>= 1;
		}

		cout << cur << ' ';
	}
}