[C++]백준 - 17435번 문제

17435번: 합성함수와 쿼리 (acmicpc.net)

17435번: 합성함수와 쿼리

 

17435번 : 합성함수와 쿼리

---

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

• f1(x) = f(x)
• fn+1(x) = f(fn(x))

예를 들어 f4(1) = f(f(f(f(1))))이다.

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

 

입력

---

첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)

다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.

다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m)

 

출력

---

주어지는 n, x마다 fn(x)를 출력한다.

 

 

---

 

생각해 볼 점

---

Sparse Table에 대한 이해가 필요합니다. 아래 블로그에서 잘 설명해주고 있습니다.

 

Sparse Table (tistory.com)

Sparse Table

 

스파스 테이블을 사용하지 않고

 

그냥 계속 재귀 함수 호출을 한다면,

 

결과가 좋지 않을 것이 뻔합니다.

 

메모리나 시간이 초과하게 되겠죠..

 

이진법을 이용해서 table을 채워나가, DP처럼 활용해봅시다.

 

table[X][i] = f(X) ^ (2 ^ i) 의 결과를 저장

 

코드

---

#include <iostream>
using namespace std;


int** table;

//재귀를 통해 value를 가져옴, 가져오면서 table에 그 결과를 저장
int get_value(int X, int sqr)
{
	if (table[X][sqr] != -1) return table[X][sqr];
	return table[X][sqr] = get_value(get_value(X, sqr - 1) -1, sqr - 1);
}

int solution(int N, int X)
{
	int sqr = 0;
	int ret = X;
    
    //이진법과 sparse 테이블 이용
	while (N)
	{
		if (N % 2) ret = get_value(ret, sqr) - 1;
		N >>= 1;
		sqr++;
	}
	return ret;
}

int main()
{
	int M;
	scanf("%d", &M);

	table = new int* [M];
	for (int i = 0; i < M; i++)
	{
		table[i] = new int[19];
		fill_n(table[i], 19, -1);
		scanf("%d", &table[i][0]);
				
	}

	int Q;
	scanf("%d", &Q);

	while (Q--)
	{
		int N, X;
		scanf("%d %d", &N, &X);
		X--;

		printf("%d\n",solution(N, X) + 1);
	}
	for (int i = 0; i < M; i++) delete[] table[i];
	delete[] table;
	return 0;
}

 

그 외

---