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

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

17435번: 합성함수와 쿼리

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    final static int log = (int) (Math.log(500000) / Math.log(2));

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());

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

        for (int i = 1; i <= log; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i-1][f[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 b = log; b > -1; b--) {
                int tmp = (1 << b); // 1101에서 제일 앞(2^3) 부터 검사
                if(n >= tmp){
                    n -= tmp; //일치하는 비트 지우고
                    x = f[b][x]; //x 업데이트
                    if(n == 0) break; //다 지웠으면 탈출
                }
            }
            sb.append(x).append("\n");
        }
        System.out.println(sb);
    }
}

💡 희소배열, DP

풀이 - 처음 시도

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int[][] f = new int[500001][m + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            f[1][i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 2; i <= 500000; i++) {
            for (int j = 1; j <= m; j++) {
                int x = f[i-1][j];
                f[i][j] = f[1][x];
            }
        }
        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());
            sb.append(f[n][x]).append("\n");
        }
        System.out.println(sb);
    }
}

 

처음엔 2차원 배열에 f_n(x) 값을 저장하는 dp 방식으로 풀려고 시도했다. row에는 n을, column에는 x를 할당했고,

f_n(x) = f_n-1(f(x)) 로 나눠서 구해가는 방식이였다. ⇒ 메모리 초과 발생

---

 

🔻 문제점 🔻 메모리 초과, 1 ~ 500000 까지 다 저장하는게 사실상 불가능함

 

⇒여기서 "희소배열"을 적절히 적용해주는 것! (연속적이지 않게 요소를 배치해도 충분히 접근 가능하다)

 

🟢 어떻게?

f_n에서, n이 짝수인 경우만 dp에 저장한다고 가정하자. 즉 f_1, f_2, f_4, f_6 ...만 저장되는 것이다. (f_1은 예외)

-   만약 쿼리에서 주어진 n이 짝수인 경우, 바로 dp[n][x]를 찾으면 된다

-   만약 n이 홀수라면, f(f_n-1(x))로 짝수 값을 사용해 홀수를 도출할 수 있다

🔥 점화식 : dp[n][x] = dp[n/2][dp[n/2][x]] (=> f_4(x) = f(f(f_2(x))) = f_2(f_2(x)) 이렇게...)
              (여기선 2의 배수만 있으므로) dp[i][j] = dp[ i-1 ][ dp[i-1][j] ] 

📌 dp[n] 부분에 2 제곱수만 들어가므로, row 방향으로 배열의 크기는 500000 → log2(500000) 로 대폭 감소함!

 

🔻 f[13][x]를 구하고 싶다면, 13 == 1101 이므로 2^0 - 2^2 - 2^3만큼 뛰어넘어야 함

      ⇒ f[0][ f[2][ f[3][x] ] ]  ⇒ 이런 방식으로 비트가 1로 일치하는 위치의 값을 찾아 x 업데이트 해 나가는 방식이다

for (int b = log; b > -1; b--) {
	int tmp = (1 << b); // 1101에서 제일 앞(2^3) 부터 검사
	if(n >= tmp){ 
    	n -= tmp; //일치하는 비트 지우고
		x = f[b][x]; //x 업데이트
		if(n == 0) break; //다 지웠으면 탈출
	}
}