[백준] 1629 곱셈 - 수학(Math) + 분할정복(DivideAndConquer) + 재귀(Recursive) JAVA

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

1629번: 곱셈

코드설명

수학 분할정복 재귀 문제입니다.

 

단순히 for문을 활용하여 곱셈을 진행할경우, B의 최대 크기는 2^31 -1 이기 떄문에 시간복잡도가 O(2^31 - 1) 이 될 것이기에 시간초과가 날것입니다.

 

그렇기에 분할정복을 통해 해당 과정들을 O( log (2^31 -1 ) ) 로 줄일 수 있습니다.

 

문제예시로 들어보겠습니다.

10 11 12

문제에서 원하는 답은 ( 10^11 ) % 12 일 값입니다.

10^11 = 10^5 * 10^5 * 10

10^5 = 10^2 * 10^2 * 10

10^2 = 10^1 * 10^1

10^1 = 10^1

 

위의 식을 활용하여 진행할 수 있습니다.

 

public static long pow(long a, long b, long mod) {
    if( b == 1) { // 지수가 1일경우 즉, 10^1 일경우 그대로 return 합니다.
        return a % mod;
    }
    long temp = pow(a, b/2, mod);
    if(b%2 == 1) {
        return (temp * temp % mod) * a % mod; //만약 홀수일경우(10^5), 10^2 * 10^2 * 10 을 통해서 10^5 로 만들어줍니다.
    }
    else {
        return temp * temp % mod; //만약 짝수일경우 (10^2), 10^1 * 10^1 을 통해서 10^2 로 만들어줍니다.
    }
}

• pow(10, 11, 12)를 함수로 시작합니다.
• 이떄 연속적으로 pow(10, 11, 12) -> pow(10, 5, 12) -> pow(10, 2, 12) -> pow(10, 1, 12) 이렇게 함수가 실행됩니다.
  • 이때 pow(10, 1, 12) 는 10 % 12 를 반환합니다.
  • 이후에 pow(10, 2, 12)는 pow(10, 1, 12)가 반환한 10 을 받은 후에 b%2 == 0 이므로 10 * 10 % 12 가 실행됩니다.
  • 이 과정을 통해서 끝까지 올라간다면, 종료됩니다.

 

 

처음에 메모리초과 및 시간초과가 났었습니다.

static int[] cache = new int[Integer.MAX_VALUE];

이유는 아래와 같이 temp값에 divideAndConquerPow(pow / 2) 처럼 값을 저장해두지 않고, 캐시값으로 처리하려했으나 4byte형 자료형인 int를 2^31 만큼 받으면 약 8GB가 됩니다.

static int divideAndConquerPow(int pow) {
    if(pow == 1) return A % C;
    int ret = 0;
    if(pow % 2 == 1) {
        ret = ( divideAndConquerPow(pow - 1) * A ) % C;
    } else if(pow % 2 == 0) {
        ret = ( divideAndConquerPow(pow / 2) * divideAndConquerPow(pow / 2)) % C; 
    }
    return ret % C;
}

 

두번째는 자료형입니다.

C를 %로 나눠주기에 자동으로 int형을 벗어나지않겠지하고 생각했으나,

temp * temp 가 작동되는 과정에서 벗어날 수 있습니다.

temp % C * temp % C 가 되더라도 이 값 자체가 int형이기에 2^31 이상의 값이 되면 값을 잃어버리는 것 입니다.

ret = ( temp * temp) % C;

 

코드

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

public class Main {
	public static long A, B, C;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	A = Long.parseLong(st.nextToken());
    	B = Long.parseLong(st.nextToken());
    	C = Long.parseLong(st.nextToken());

    	System.out.println(pow(A, B, C));
    }
    
    public static long pow(long a, long b, long mod) {
    	if( b == 1) { // 지수가 1일경우 즉, 10^1 일경우 그대로 return 합니다.
    		return a % mod;
    	}
    	long temp = pow(a, b/2, mod);
    	if(b%2 == 1) {
    		return (temp * temp % mod) * a % mod; //만약 홀수일경우(10^5), 10^2 * 10^2 * 10 을 통해서 10^5 로 만들어줍니다.
    	}
    	else {
    		return temp * temp % mod; //만약 짝수일경우 (10^2), 10^1 * 10^1 을 통해서 10^2 로 만들어줍니다.
    	}
    }
    
}

 

정답코드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 {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		System.out.println(divideAndConquerPow(B));
	}
	
	static long divideAndConquerPow(int pow) {
		if(pow == 1) return A % C;
		
		long ret = 0;
		if(pow % 2 == 1) {
			ret = ( divideAndConquerPow(pow - 1) * A ) % C;
		} else if(pow % 2 == 0) {
			long temp = divideAndConquerPow(pow / 2) % C;
			ret = ( temp * temp) % C; 
		}
		return ret % C;
	}
	
}