BOJ_17435_합성함수와 쿼리 (Java)

[Gold I] 합성함수와 쿼리 - 17435

문제 링크

성능 요약

메모리: 103124 KB, 시간: 900 ms

분류

자료 구조, 희소 배열

제출 일자

2025년 2월 5일 05:07:06

문제 설명

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

• f₁(x) = f(x)
• f_n+1(x) = f(f_n(x))

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

n과 x가 주어질 때 f_n(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마다 f_n(x)를 출력한다.

문제 풀이

희소 배열을 공부했다.

희소 배열이란?

2의 거듭제곱 단위로 건너뛰는 결과를 미리 저장해두는 배열입니다 dp[k][x] = x에서 시작해서 2^k번 이동했을 때의 도착점

예시로 이해하기

f = [3, 3, 5, 4, 3] (인덱스는 1부터 시작)

1. dp[0][x] = 한 번 이동

   • dp[0][1] = 3 (1→3)
   • dp[0][2] = 3 (2→3)
   • dp[0][3] = 5 (3→5)

2. dp[1][x] = 두 번 이동

   • dp[1][1] = 5 (1→3→5)
   • dp[1][2] = 5 (2→3→5)
   • dp[1][3] = 3 (3→5→3)

3. p[2][x] = 네 번 이동

   • dp[2][1] = 3 (1→3→5→3→5)

이런 식으로 2의 거듭제곱 단위로 몇 번 이동했을 때의 결과를 미리 계산해두는 것이 희소 배열의 핵심입니다.

장점

• n번 이동해야 할 때, n을 이진수로 분해해서 필요한 부분만 사용
• 예: 7번 이동 = 4번 이동 + 2번 이동 + 1번 이동 (7 = 4 + 2 + 1)

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_17435_합성함수와쿼리/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int m = Integer.parseInt(br.readLine());
        int[][] dp = new int[19][m+1]; // 2^18 > 500000 이므로 19도 충분함

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= m; i++) {
            dp[0][i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<19; i++) {
            for(int j=1; j<=m; j++){
                dp[i][j] = dp[i-1][dp[i-1][j]];
            }
        }

        int q = Integer.parseInt(br.readLine());
        while(q--> 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            for(int i=0; i<19; i++){
                if((n & (1<<i)) != 0) x = dp[i][x];
            }
            sb.append(x).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

---

입출력 가장빠르게 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int m, q, n, x;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        m = read();
        int[][] dp = new int[19][m+1];

        // f(x) 입력 받기
        for(int i = 1; i <= m; i++) {
            dp[0][i] = read();
        }

        // 희소 배열 계산
        for(int i=1; i<19; i++) {
            for(int j=1; j<=m; j++){
                dp[i][j] = dp[i-1][dp[i-1][j]];
            }
        }

        q = read();
        while(q--> 0) {
            n = read();
            x = read();

            for(int i=0; i<19; i++){
                if((n & (1<<i)) != 0) x = dp[i][x];
            }
            sb.append(x).append("\n");
        }
        System.out.println(sb);
    }
    public static int read() throws IOException {
        int n = 0;
        boolean isNegative = false;
        int c;
        while ((c = System.in.read()) <= 32) ;
        if (c == '-') {
            isNegative = true;
            c = System.in.read();
        }
        do n = (n << 3) + (n << 1) + (c & 15);
        while ((c = System.in.read()) > 32);
        return isNegative ? -n : n;
    }
}

로직 같은 코든데

이정도 차이난다.