[Algorithm/Java] 백준 1629번 - 곱셈

---

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

---

📌 문제

문제 유형

• 수학
• 분할정복

📘 문제 설명

🔍 문제 풀이

문제 해결 절차

지수 B가 크므로 반복문으로 A를 B번 곱하면 시간 초과 발생 -> 따라서 분할 정복을 사용해 ` O(log B)`로 계산해야 한다.

a=2, b=10이라고 가정해보자.

제곱은 다음과 같이 분할이 가능하다.

이렇게 재귀함수로 b가 0이 될 때까지 절반으로 계속 나눠서 아래 공식을 적용하면 된다.

• b가 짝수일 때 : half * half
• b가 홀수일 때 : half * half * a

재귀 호출의 깊이만큼 if (b % 2 == 0) 분기가 호출되고,
올라오면서 half * half 또는 half * half * a 식으로 곱셈이 누적된다.

재귀 호출 도중마다 C로 나머지 연산을 수행해 오버플로우를 방지할 수 있다.

예시

pow(2, 4, 13)
→ half = pow(2, 2, 13)
→→ half = pow(2, 1, 13)
→→→ half = pow(2, 0, 13) → return 1
→→ return (1 * 1 * 2) % 13 = 2
→ return (2 * 2) % 13 = 4

💻 전체 코드

a를 b번 곱해야 하는데, 결국 a를 b번 곱한 결과를 간접적으로 만들어낸다.

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

public 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));
    }

    public static long pow(long a, long b, long mod){
        if(b==0) return 1;

        long half = pow(a, b / 2, mod);
        if (b % 2 == 0) return half * half % mod; //  a^(b/2) * a^(b/2) = a^b
        else return (half * half % mod) * a % mod;
    }
}