[Algorithm] 분할 정복을 이용한 거듭제곱과 [백준 1629] 곱셈

분할 정복

둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산함.

(해당 사진은 병합 정렬에서 풀었던 과정 - 병합 정렬도 분할 정복 알고리즘에 속함.)

문제 풀기

문제 접근

자연수 A를 B번 곱해야 하기 때문에 A^B 형태를 구하는 문제가 되며, 수가 커질 수 있기 때문에 C로 나눠 나머지를 구하는 게 최종 답이 됨.
해당 문제에서는 주어지는 자연수의 범위가 크기 때문에 한 번에 곱하는 것이 아닌, 분할 정복을 통해 거듭제곱을 해야 함.

이때 지수가 홀수냐 짝수냐에 따라서 분해하는 방식이 달라짐.
지수가 짝수인 경우는 A^{지수/2} 두 개를 곱해도 값이 나오지만,
홀수의 경우 A만큼이 부족하기 때문에 A^{지수/2} 두 개에 A를 하나 곱함.
이 분해는 지수가 0이 될때까지 반복되며, 지수가 0이 되면 1이 반환되도록 함.
반환된 값이 그 전 식에 대입하면서 식을 풀어가고, 마지막에는 A^B의 값을 알 수 있게 됨.

코드

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 st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        bw.write(pow(a, b, c) + "");
        bw.flush();
        br.close();
        bw.close();
    }

    private static long pow(long a, long b, long c) {
        if (b == 0) return 1;

        long returnValue = pow(a, b/2, c) % c;

        if (b % 2 == 0) return (returnValue * returnValue) % c;
        return ((returnValue * returnValue) % c * (a % c)) % c;
    }
}

참고 링크

https://velog.io/@turtle601/분할정복
https://namu.wiki/w/분할 정복 알고리즘
https://sskl660.tistory.com/76