[Baekjoon Online Judge] 1629. 곱셈 // 해설 (Java)

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

문제

 

---

핵심

결론부터 말하면 재귀 함수를 이용한 분할 정복으로 풀었습니다.

이 둘에 대해 잘 모른다면 먼저 학습한 후에 풀어보는 것도 좋을 것 같습니다.

 

거듭제곱을 단순 반복문으로 계산하면 O(B)의 시간복잡도를 가지게 됩니다.

B는 최대 2,147,483,647이므로 시간 초과

 

결국 시간 복잡도를 줄이라는 문제인데 

분할 정복을 사용하면 O(logB)의 시간 복잡도를 가집니다.

a*a*a*a*a*a = (a*a*a) * (a*a*a) 라는 성질을 이용해서

중복되는 계산을 반으로 줄이면 이렇게 log 시간 복잡도를 가지게 됩니다.

---

구현

코드 (Java)

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

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        System.out.println(pow(a, b, c));
    }

    static long pow(int x, int n, int mod) {

        if (n == 0) {
            return 1;
        }

        long y = pow(x, n / 2, mod);

        y = y * y % mod;

        if (n % 2 == 1) {
            y = y * x % mod;
        }

        return y;
    }
}