[백준 17435] 합성함수와 쿼리

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

17435번: 합성함수와 쿼리

 

 

가능한 정점의 개수는 최대 20만개, 이동 횟수는 최대 50만개이므로

단순히 f(x) 함수 값을 계속 계산하는 방법으로 풀이한다면 당연히 시간초과가 난다..

 

시간 복잡도를 줄이기 위하여

희소 배열을 사용하고,

이를 적용하여 이동 횟수에 대한 탐색을 log(n)으로 줄일 수 있다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int MAX=500000+1;
    static int MAXROW = (int) (Math.log10((double) MAX) / Math.log10(2.0)) + 1;

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.valueOf(br.readLine());
        int sparseArr[][] = new int[MAXROW][M+1];   //희소 배열
        StringTokenizer stk = new StringTokenizer(br.readLine());

        /** sparseArr **/
        //sparseArr[0]
        for (int i = 1; i <= M; i++) {
            sparseArr[0][i] = Integer.valueOf(stk.nextToken());
        }

        int ncol;
        for (int row = 1; row < MAXROW; row++) {
            for (int col = 1; col <= M; col++) {
                ncol = sparseArr[row - 1][col];
                sparseArr[row][col] = sparseArr[row-1][ncol];
            }
        }
        /****/

        int n, x;
        int Q = Integer.valueOf(br.readLine());     //query의 개수
        for (int i = 0; i < Q; i++) {
            stk = new StringTokenizer(br.readLine());
            n = Integer.valueOf(stk.nextToken());
            x = Integer.valueOf(stk.nextToken());

            System.out.println(returnQuery(sparseArr,n, x));

        }
    }

    //밑이 2인 log
    private static double log(int x) {
        return Math.log10((double) x) / Math.log10(2.0);
    }

    private static int returnQuery(int arr[][], int n, int x) {
        int returnValue;
        int move = n;
        int scol = x;
        int srow;

        while (move != 0) {
            srow = (int) log(move);
            move -= (int) (Math.pow(2.0, srow));
            scol = arr[srow][scol];
        }

        returnValue = scol;
        return returnValue;
    }
}