[알고리즘] 백준 > #17435. 합성함수와 쿼리

문제링크

백준 #17435. 합성합수와 쿼리

풀이방법

아무런 알고리즘, 테크닉을 사용하지 않고 문제를 푼다고 생각해봅시다. O(QN)의 시간복잡도를 갖겠네요! 시간제한인 1초를 쉽게 넘기겠죠? 이 문제를 해결하기 위해 일부 함수 결과를 미리 테이블에 저장하는 전처리 과정을 구현했습니다!

이렇게 전처리 과정을 통해 배열 내 구간의 쿼리를 빠르게 수행할 수 있도록 하는 자료구조를 희소테이블, Sparse Table이라고 합니다. "일부 함수 결과를 미리 테이블에 저장" 이라고 했는데요, 이 "일부"를 2^k로 설정하였습니다. 미리 탐색하는 값이 너무 작거나 크면 그 효과가 미미하기 때문에 이렇게 2^k로 진행합니다~

shortCuts 라는 배열에 함수실행결과를 18번(2^k < N인 k중 가장 큰 수)까지 저장한 뒤 이 테이블을 사용해 쿼리 결과를 알아내는데요, 이 테이블을 어떻게 사용해야할까요? 비트마스킹을 사용합니다. 입력된 n 값을 비트로 나타내 그 값이 1인 경우에(ex. n = 11, 11 = 1011 = 2^0 + 2^1 + 2^3) shortCuts[bit][n]으로 이동하는 겁니다! 모든 1인 값에 대해 이동을 진행하면 찾고자 하는 결과에 도달할 수 있습니다. 저한테는 조금 어려운 자료구조였습니다 T-T

코드

import java.util.Scanner;

public class FunctionAndQuery {
    static final int MAX_K = 19; // 2^19 > 500,000
    static final int MAX_M = 200001;
    static int[][] shortCuts = new int[MAX_K][MAX_M];
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        for (int i = 1; i <= m; i++) shortCuts[0][i] = sc.nextInt();
        for (int i = 1; i < MAX_K; i++) {
            for (int j = 1; j <= m; j++) {
                shortCuts[i][j] = shortCuts[i - 1][shortCuts[i - 1][j]];
            }
        }

        StringBuilder result = new StringBuilder();
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int n = sc.nextInt();
            int x = sc.nextInt();

            for (int bit = 0; bit < MAX_K; bit++) {
                if ((n & (1 << bit)) > 0) {
                    x = shortCuts[bit][x];
                }
            }
            result.append(x + "\n");
        }

        System.out.print(result.toString());
    }
}