[백준] 1629. 곱셈

문제 링크

[백준] 1629. 곱셈

풀이 과정

거듭 제곱을 분할 정복을 이용하여 표현해서 풀 수 있었습니다.

$$pow(A, B) = \begin{cases} A, & \text{$n = 1$} \\ pow(A, B/2)^2, & \text{if $B$ is even}\\ pow(A, B/2)^2 * A, & \text{if $B$ is odd} \end{cases}$$

제곱 횟수 B 가 주어지면, 반으로 계속 나누어 그 값을 얻어 본 계산에 사용하게 됩니다.

입력으로 4 1 2 와 같이 제곱 횟수가 한 번으로 주어지면 나머지 연산을 거치지 않고 바로 A를 리턴하기 때문에, 답을 출력하는 곳에 나머지 연산을 한 번 더 작성해줌으로써 예외를 처리할 수 있었습니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int A, B, C;
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();

        System.out.println(pow(A, B, C) % C);
    }

    public static long pow(int A, int B, int C) {
        if (B == 1) return A;
        else {
            long half = pow(A, B / 2, C);
            if (B % 2 == 0) return half * half % C;
            else return half * half % C * A % C;
        }
    }
}