[BOJ] 1629. 곱셈

재귀를 이용하는 기초적인 문제이다. 주어진 숫자의 범위가 2,147,483,647이므로 일반적인 방법으로 접근하면 시간초과가 발생할수밖에 없다.

따라서 재귀를 사용해야하는데 위와 같은 성질을 이용하여 재귀를 사용해준다. 즉, 지수를 계속 제곱해준다는 개념으로 접근하여 B의 값까지 도달하는 것을 구하는 방법으로 해결하면 되는 문제이다. 기저조건으로는 B의 값이 0이 될때를 사용하였다.

또한 보통 분할정복을 사용하는 알고리즘은 3가지의 구성요소를 가지고있다.
1. 문제를 더 작은 문제로 분할하는 과정 (divide)
2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge)
3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

 

package chap06;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1629_곱셈 {
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long A=Integer.parseInt(st.nextToken());
        long B=Integer.parseInt(st.nextToken());
        long C=Integer.parseInt(st.nextToken());
        
        System.out.println(func(A,B,C));
    }
    
    static long func(long A,long B,long C) {
        if(B==0) {
            return 1;
        }
        else {
            long value = func(A,B/2,C);
            value=value*value %C;
            
            if(B%2==0) {
                return value;
            }
            else {
                return value*A%C;
            }
        }
    }
 
}