[백준] 1629번: 곱셈

문제

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

알고리즘

처음에는 재귀함수로 계산을 했는데 주어지는 값이 커지면 메모리 초과가 발생하는 것 같아서 어떻게 바꿀 수 있을까 고민했다.

만약 A가 10이고 B가 4라고 가정해보자
가장 간단한 것은 그냥 반복문을 사용해서 10을 4번 곱하는 것이다.
하지만 그래서 메모리 초과가 발생한 것이니 다른 접근 방법을 사용해보자.
10의 네제곱은 10을 제곱한 것의 제곱과 같다. 즉, 10의 제곱 값을 구하면 10의 네제곱은 쉽게 구할 수 있다.
이렇게 B가 짝수라면 A의 B/2제곱을 구해서 제곱하면 된다.

만약 A가 10이고 B가 5라고 가정해보자.

B가 홀수인 경우에는 이렇듯 A의 (B-1)/2 제곱을 구해서 제곱하고, A를 한 번 더 곱해주면 된다.

여기서 핵심은 B가 짝수인지 홀수인지 확인하는 것이다.
이 방법을 활용하여 메모리 사용량을 줄일 수 있다!

코드

import java.util.Scanner;

public class Baekjoon1629 {
    static long A, B, C;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextLong();
        B = sc.nextLong();
        C = sc.nextLong();
        
        System.out.println(pow(A, B));
    }

    static long pow(long base, long exp) {
        if (exp == 0) return 1;
        long half = pow(base, exp / 2) % C;

        if (exp % 2 == 0) {
            return (half * half) % C;
        } else {
            return (((half * half) % C) * base) % C;
        }
    }
}

마무리

무식한 방법으로 시도했지만.. 메모리 초과로 계속 틀렸다.
다시 수학적인 원리로 돌아갔다.
역시 알고리즘을 하면할수록 어렵다 ..