[BOJ_1629 | Divide & Conquer] 곱셈

풀이

처음에 문제를 접근 할 때에는 그냥 반복문을 n번정도 돌리면서 곱하고, 

그 값이 c보다 커지면 한번씩 나누어 나머지를 구해주고

이렇게 계산을 반복하면 되는 것 아닌가? 하고 생각했다. 

이렇게 생각하면 굉장히 단순하고 구현또한 어렵지 않았기 때문에 왜 정답률이 30%가 채 안되는지 이해할 수 가 없었지만..

Online Judge에 코드를 넣고 돌려본 뒤에 시간초과가 뜨는 걸 확인하고

아 O(n)으로 풀면 안되는 문제였구나 라는 생각이 들었다.

정수의 거듭제곱을 구하는 알고리즘은 여러가지가 있다.

그 중 가장 단순하고 구현하기 쉬운 알고리즘은 물론 a를 b번 반복하면서 곱해주는 것이지만

시간복잡도가 O(n)으로 비교적 오래 걸리는 알고리즘이다.

그래서 나온 것이 바로 Divide & Conquer 방법을 사용한 알고리즘이다.

재귀를 사용해서 구해야 할 차수를 절반씩 나누어 각각 구하게 하는 것이다.

예를 들어 2^16차 항을 구해야 하는 경우

O(n)의 복잡도를 가지는 알고리즘에서 2를 16번 곱하므로 16번의 계산이 필요하다.

하지만, Divide & Conquer를 이용하면

2^8을 호출해 그 둘을 곱할때 1번

2^8에서 2^4를 호출해 그 둘을 곱할 때 1번

2^4에서 2^2를 호출해 곱할때 1번

2^2에서 2^1을 호출해 곱할때 1번

이렇게 4번의 연산만 수행하게 된다.

즉 O(log N)의 복잡도를 가지는 알고리즘이 되는 것이다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_1629 {
    public static void main(String[] args) throws IOException{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
 
        bw.write(pow(a, b, c)+"\n");
        bw.flush();
        bw.close();
    }
    
    //Divide & Conquer Algorithm Using Recursion.
    public static long pow(int a, int b, int c){
        if(b==0) return 1;
        long n = pow(a, b/2, c);
        long temp = n*n%c;
        if(b%2 == 0) return temp;
        else return a*temp%c;
    }
}