[Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께

Sparse Table (스파스 테이블) 특징 

1. 방향 그래프 입니다.
2. 모든 점이 목적지가 있습니다.
3. 그 점을 타고 새로운 점으로 갑니다.
4. 2의 제곱근으로 도착한 점을 저장합니다.
   (1번, 2번, 4번, 8번 이동에 대한 배열을 모두 저장합니다.)

 

예제를 풀면서 설명하겠습니다. 

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

17435번: 합성함수와 쿼리

이 문제는 함수 f(x)가 있을 때 f3(x)는 < y= f(x) ---->  z = f(y) ----> w = f(z) ----> result = w > 함수f(x)의 결과값을 다시 함수f(x)에 넣는걸 n번 반복하는 문제 입니다.

이 처럼 f(x)란 y라는 방향성을 가진 그래프로 표현이 가능합니다. 

아래 그림은 1번쨰는 <2의 0승> 2번째는 <2의 1승> 3번째는 <2의 0승 후 2의 1승>을 한 결과 입니다. 

이를 테이블로 정리하면 아래와 같습니다. 

Table[x][y]	[1]	[2]	[3]	[4]	[5]
[0]	3	3	5	4	3
[1]= 2의 0승	5	5	3	4	5
[2]= 2의 1승	3	3	5	4	3
[3]= 2의 0승 + 2의 1승	5	5	3	4	5

 

Q. 왜 2의 제곱근일까?

2의 제곱근은 모든 수를 표현 할 수 있기 때문입니다. 

1	2	3	4	5	6	7	8	9	10
0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
1000		1001		1002		1,003		1004
0011 1110 1000		0011 1110 1001		0011 1110 1010		0011 1110 1011		0011 1110 1100

문제에서 n이 1 ≤ n ≤ 500,000 사이의 수 이므로, 아래와 같은 범위를 가지게 됩니다. 

따라서 x는 0 ~ 18사이의 값이 될겁니다. 

저희는 SparseTable[0][x]에 초기값을 넣었으므로 SparseTable[19][x] 까지 사용하면 되겠죠 ? 

 

#include <iostream>
#include <vector> 
using namespace std;
int SparseTable[20][200'001];

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	int m;
	cin >> m;
	vector<int> vec;
	for (int i = 1; i <= m; ++i)
	{
		int fm;
		cin >> fm;
		SparseTable[0][i] = (fm);
	}

	for (int i = 1; i < 20; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			int temp = SparseTable[i - 1][j]; 
			SparseTable[i][j] = SparseTable[i - 1][temp];
		}
	}
	int q;
	cin >> q;

	while (q--)
	{
		int n, x;
		cin >> n >> x;
		int idx = x;
		for (int k = 0; k < 20; k++)
		{
			if (n & (1 << k)) {
				idx = SparseTable[k][idx];
			}
		}
		cout << idx << "\n";
	}
	return 0;
}

 

끝.

ps. 요즘 짤툰 - 짐승친구들이 너무 재미있다. 김덕배 너무 귀여워 ~~!!!!

[출처] 짤툰 - 짐승친구들 어서와 새대갈 편에서..