문제
함수 f가 {1, 2, ..., m}에서 {1, 2, ..., m}으로의 함수로 주어질 때, 쿼리 (n, x)에 대해 f를 n번 합성한 fn(x) 값을 구하라.
입력
첫째 줄에 m(1 ≤ m ≤ 200,000), 둘째 줄에 f(1)부터 f(m)까지 공백으로 구분하여 주어진다. 셋째 줄에 쿼리 수 Q(1 ≤ Q ≤ 200,000), 이후 Q줄에 각각 n과 x가 주어진다 (1 ≤ n ≤ 500,000, 1 ≤ x ≤ m).
출력
각 쿼리마다 fn(x)를 한 줄에 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 1 2 2 1 1 2 1 | 3 2 |
풀이
n이 최대 500,000이므로 단순 반복은 시간 초과가 발생한다. 희소 배열(Sparse Table)을 이용하여 전처리 후 각 쿼리를 O(log n)에 처리한다.
dp[i][j]를 "j에서 f를 2^i번 적용한 결과"로 정의한다dp[0][j] = f(j)로 초기화한다dp[i][j] = dp[i-1][dp[i-1][j]]로 점화식을 채운다 (2^i = 2^(i-1) + 2^(i-1))- 쿼리 (n, x)에 대해 n을 이진수로 분해하여 해당 비트가 켜진 위치의 dp값을 순차 적용한다
핵심 아이디어: 희소 배열의 "배 건너뛰기(doubling)" 기법으로, 전처리 O(m log n) 후 각 쿼리를 O(log n)에 답할 수 있다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day65BOJ17435합성합수SparseTable연습 { // 17435 합성합수, sparse table 공부
static final int log = 19; // 주어진 N의 최대값은 500_000, 2진 bit로 19레벨로 정한다.
static int N, Q, x;
static int[][] dp; // 주어진 함수를 그대로 반복하면, 시간초과 테이블을 미리 작성하여 활용한다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
dp = new int[log + 1][N + 1]; // N의 번호는 1부터
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++)
dp[0][i] = Integer.parseInt(st.nextToken());
// 입력받은 값은 0번 자리에 행에 입력을 받는다.
for (int i = 1; i < log + 1; i++) {
for (int j = 1; j < N + 1; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
} // 1행 이후의 행들의 값을 미리 작성한다.
}
Q = Integer.parseInt(br.readLine());
for (int q = 0; q < Q; q++) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
for (int i = 0; i < log; i++) {
if ((n & 1 << i) > 0) { // n을 비트 읽어 값에 대입
x = dp[i][x];
} // sparse table 처리된 값을 호출한다.
}
sb.append(x).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(m log N + Q log N)
- 공간: O(m log N)