백준 - 1629 곱셈(Java)

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

1629번: 곱셈

 

분할과 정복 문제입니다.

분할과 정복은 크게 세 단계로 나눌 수 있습니다.

1. Divide : 문제 분할
2. Conquer : 쪼개진 작은 문제 해결
3. Combine : 해결된 작은 문제를 다시 합침

위 특성 때문에 Top-Down 재귀 방식으로 해결해야 합니다.

문제 자체는 간단하지만 난이도에 비해 정답률이 매우 낮습니다.

그 이유는 수학의 두 가지 법칙을 사용해야 합니다.

1. 지수 법칙 : a^b = a^(b/2) * a^(b/2)
2. 나머지 법칙 : (a*b)%c = (a%c * a%c) % c

a^b를 구할 때, a를 b번만큼 반복을해서 구하면 시간 복잡도는 O(N)이 됩니다.

이 문제의 입력 값이 매우 크기 때문에 이 방법은 불가능 합니다.

따라서 시간 복잡도가 O(logN) 방식인 분할과 정복 문제로 해결해야 합니다.

지수 법칙에 의해 제곱 계산은 다음과 같은 세 가지로 구분할 수 있습니다.

 

1. b = 1일 떄,         a^b = 1
2. b%2 == 0일 때, a^b = a^(b/2) * a^(b/2)
3. b%2 == 1일 때, a^b = a * a^(b-1)

위 세 가지 조건을 고려하여 재귀 함수를 구현하면 됩니다.

단, 입력의 범위가 매우 크기 때문에 나머지 법칙에 의해 각 연산에 나머지 연산을 추가해야 합니다.

(1 <= a, b, c <= 2,147,483,647)

 

[구현 코드]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    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 stz = new StringTokenizer(br.readLine(), " ");

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

        // a^b
        long ans = divide(a, b, c);

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

    /*
    * 지수 법칙에 의해
    * 시간 복잡도 : O(logN)
    * b = 1     , a^b = a
    * b % 2 == 0, a^b = a^(b/2) * a^(b/2)
    * b % 2 == 1, a^b = a * a^(b-1)
    * */
    private static long divide(long a, long b, long mod) {
        if (b == 1) return a % mod;
        if (b % 2 == 0) return twice(divide(a, b / 2, mod)) % mod;
        return a * divide(a, b - 1, mod) % mod;
    }

    private static long twice(long a) {
        return a * a;
    }
}