[백준] 13171 A - 분할 정복을 이용한 거듭제곱(Divide And Conquer) + 수학(Math) + 비트마스킹(BitMask) JAVA

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

코드설명

분할 정복을 이용한 거듭제곱(Divide And Conquer) + 수학(Math) + 비트마스킹(BitMask) 을 활용합니다.

 

단순하게 분할정복을 이용하여 계산을 시도하면 시간초과가 발생합니다.

그 대신에, 빠른 거듭제곱의 합을 활용하여야 합니다. 문제의 지문에 제시된 대로, 지수연산을 활용해야 합니다.

 

1. 먼저 2^64 번 제곱이 최고의 수이므로, long[] cache = new long[64]로 선언합니다.

이떄 64는 단순히 64가 아니라, 2^64 를 의미하는 것 입니다.

 

2. 점화식을 활용해 A^1, A^2, A^4, A^8... 을 계산해나갑니다.

이떄 A^1 은 cache[0]

A^2은 cache[1].

A^3 는 Cache[2] 를 의미합니다.

 

수학적으로 이야기하면 log2(X) = Cache의 Index입니다.

long[] cache = new long[64];
cache[0] = A % MOD;
for(int i=1; i < 64; i++) {
    cache[i] = (cache[i-1] * cache[i-1]) % MOD;
}

 

3. 지수 X와 비트마스킹을 하여 1, 2, 4, 8, 16, 32... 순으로 해당 지수가 이루어져 있는지 확인합니다.

만약 이루어져있다면, 지수법칙에 의하여 서로 곱해주면 답이 됩니다.

long result = 1;
for(int i=63; i>=0; i--) {
    if ((X & (1L << i)) != 0) {
        result = (result * cache[i] % MOD);
    }
}

 

코드

정답코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static StringBuilder sb = new StringBuilder();
    private static final int MOD = (int) 1e9 + 7;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long A = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long X = Long.parseLong(st.nextToken());
        
        long[] cache = new long[64];
        cache[0] = A % MOD;
        for(int i=1; i < 64; i++) {
            cache[i] = (cache[i-1] * cache[i-1]) % MOD;
        }
        
        long result = 1;
        for(int i=63; i>=0; i--) {
            if ((X & (1L << i)) != 0) {
                result = (result * cache[i] % MOD);
            }
        }
        
        System.out.println(result);
    }
    
}

 

분할정복을 이용해본 코드입니다. 시간초과가 발생합니다. Cache를 적용하지 못하는 이유는 X의 크기가 1<=X<=1e18 이기 떄문입니다.  만약 Cache를 적용할 수 있었다면 너무 많은 메모리가 사용되긴하겠지만 작동은 할 것입니다. (배열 Size는 32비트까지만 가능)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache;
    private static StringBuilder sb = new StringBuilder();
    private static final int MOD = (int) 1e9 + 7;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Long A = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Long X = Long.parseLong(st.nextToken());
        Arrays.fill(cache, -1);
        
        System.out.println(func(A, X) % MOD);
    }
    
    public static long func(long A, long X) {
    	if(X == 1) return A;
    	if(X % 2 == 1) return (func(A, X-1) * A ) % MOD;
    	return (func(A, X/2) * func(A, X/2) ) % MOD;
    }
    
}

 

시간초과 코드 2 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    private static long[] cache = new long[64];
    private static StringBuilder sb = new StringBuilder();
    private static final int MOD = (int) 1e9 + 7;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long A = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long X = Long.parseLong(st.nextToken());
        
        Arrays.fill(cache, -1);
        
        long result = 1;
        for(int i=63; i>=0; i--) {
            if ((X & (1L << i)) != 0) {
                result = (result * func(A, 1L << i) ) % MOD;
            }
        }
        
        System.out.println(result);
    }
    
    public static long func(long A, long X) {
    	if(X == 1) return A;
    	if(X % 2 == 1) return (func(A, X-1) * A ) % MOD;
    	return (func(A, X/2) * func(A, X/2) ) % MOD;
    }
    
}