boj, 백준) 17435. 합성함수와 쿼리 (C / C++)

1. 문제 링크

www.acmicpc.net/problem/17435

17435번: 합성함수와 쿼리

2. 문제 개요

함수 f : {1, 2, ...., m} → {1, 2, ..., m}이 있다. 이때 f_n : {1, 2, ...., m} → {1, 2, ..., m}을 다음과 같이 정의한다.

 

- f_1(x) = f(x)

- f_n+1(x) = f(f_n(x))

 

n과 x가 주어질 때 f_n(x)를 계산하는 쿼리를 수행하는 프로그램을 작성.

 

3. 문제 힌트

m은 최대 200,000이고 n은 500,000이다. 그리고 들어오는 쿼리의 개수는 최대 200,000.

 

여러 생각을 해보자,

f_n(m)을 dp[n][m]이라고 생각하고 모든 값들을 갖고 있으려고 하면 엄청난 수의 배열이 필요하게 된다. (X)

 

그럼,

쿼리가 들어올 때, 재귀적으로 f_n(x)값을 구하면? 한 쿼리당 O(n)의 시간이 소요될 것이다. O(qn)은 시간 초과(X)

 

그러면...

모든 f_n(x)값을 가지고 있지 않으면서도 빠르게 구할 수 있는 방법은 없을까?

 

log....

4. 문제 풀이

위에 썼던 dp[n][m]에서 n을 50만이 아닌 log2(500000)으로 해서 데이터를 갖고 있어도 된다.

 

예를 들어, n이 11이라고 해보자,

2진수로 나타내면 1011이다. 이런 경우 f_8(f_2(f_1(x)))로 나타낼 수 있다.

그래서 매 쿼리마다 O(n)의 시간이 걸리는 것을 O(log2(n))으로 줄일 수 있게 된다.

대신에 log2(n)의 올림 한 값 x m 만큼은 공간을 차지하게 된다.

 

처음 주어지는 배열의 값은 0번째 자리(LSB) 값으로

dp[0][m]에 값을 넣어주면 된다.

 

dp[1][x] = dp[0][dp[0][x]]로 정의할 수 있다.

dp[2][x] = dp[1][dp[1][x]]이고,

 

dp[k][x] = dp[k-1][dp[k-1][x]]이다.

 

숫자로 예를 들면 f_8(x) = f_4(f_4(x))로 나타낼 수 있다.

위의 점화식(?)을 보고 반복문을 작성하자.

 

이렇게 미리 테이블(sparce table)을 구해놓은 뒤 쿼리 때마다 right shift를 해주며 값이 0이 아닐 때까지 반복해서 구해주면 된다.

 

 

참고로 LCA도 이런 구조를 사용한다.

 

5. 코드

#include <cstdio>
#include <cmath>
using namespace std;

int m, len;
int f[19][200001];	//log2(500,000) 18.xxx -> 19

int main()
{
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i)
		scanf("%d", &f[0][i]);

	len = (int)ceil(log2(500000));	 // n<=500000

	for (int i = 0; i < len; ++i) 
		for (int j = 1; j <= m; ++j) 
			f[i + 1][j] = f[i][f[i][j]];
		
	int q;
	scanf("%d", &q);

	while (q--)
	{
		int n, x;
		scanf("%d %d", &n, &x);

		for (int i = 0; n != 0; ++i) {

			if (n % 2 == 1) 
				x = f[i][x];
			
			n = n >> 1;
		}

		printf("%d\n", x);
	}

	return 0;
}

6. 결과