[백준 1629] 곱셈 (S1) — 메모리 초과에서 분할정복 모듈러 거듭제곱까지

[S1] 1629 곱셈 문제 바로 가기

1. 문제 요약

정수 A, B, C가 주어졌을 때,

(A^B) % C

 

를 출력하는 문제다.

 

여기서 핵심은 B가 매우 클 수 있다는 점이다.

단순히 A를 B번 곱하는 방식은 시간/메모리 측면에서 절대 통과할 수 없다.

---

2. 처음 시도: 단순 재귀의 함정 (메모리 초과)

처음에는 다음처럼 b를 1씩 줄이며 곱하는 재귀를 작성했다.

return a * func(a, b-1);

 

왜 메모리 초과가 나는가?

이 방식은 재귀 호출이 B번 쌓이는 선형 재귀( O(B) )다.

• B가 크면 호출 스택이 끝없이 쌓인다.
• Java는 재귀 깊이가 커지면 스택 메모리가 터지며 보통 StackOverflowError가 발생한다.
• 백준에서는 이런 상황이 “메모리 초과”로 판정되는 경우가 많다.

즉, 단순 재귀는 스택 메모리 때문에 먼저 죽고, 설령 스택이 버틴다 해도 시간이 절대 안 된다.

---

3. 문제 핵심 [1]: “거듭제곱을 반으로 쪼개라” (분할정복)

이 문제의 정답 접근은 빠른 거듭제곱(Exponentiation by Squaring) 이다.

지수 법칙 활용

• A^(m+n) = A^m * A^n
• 특히 B를 반으로 나누면:
  • B가 짝수: A^B = (A^(B/2))^2
  • B가 홀수: A^B = (A^(B/2))^2 * A

이렇게 하면 매 단계마다 지수가 절반으로 줄어들어

• 시간복잡도는 O(log B)
• 재귀 깊이도 log B 수준이라 스택도 안전하다.

---

4. 문제 핵심 [2]: 모듈러 연산은 “중간중간” 적용해야 한다

거듭제곱은 값이 너무 커져서 long 범위를 쉽게 넘는다.

그래서 계산 과정에서 계속 % C를 적용한다.

 

모듈러 성질

(a * b) % c = ((a % c) * (b % c)) % c

 

즉, 중간 곱셈마다 % C로 줄여야 오버플로우 위험도 줄고, 결과도 정확히 유지된다.

---

5. 최종 풀이 코드 (완성본)

아래는 최종적으로 통과 가능한 코드다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static long C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        C = Long.parseLong(st.nextToken());

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

    // === 고려해야할 내용 ===
    // 지수 법칙 활용 a^(m+n) = a^m * a^n
    // 모듈려 연산 활용 (a * b) % c = {(a % c) * (b % c)} % c
    // int -> long
    public static long pow(long a, long exponent) {

        // 지수가 1인경우 a^1 이므로 a를 그대로 리턴한다.
        if (exponent == 1) {
            return a % C;
        }

        long temp = pow(a, exponent / 2);

        // 지수가 홀수인 경우
        // a^(exponent / 2) * a^(exponent / 2) * a 이므로
        // a를 한번 더 곱해줘야한다.
        // a^ 11 = a^5 * a^5 * a
        if (exponent % 2 == 1) {
            return (temp * temp % C) * a % C;
        }

        // 지수가 짝수인 경우
        return temp * temp % C;
    }
}

---

6. 동작 방식 예시로 이해하기

예를 들어 A^11을 구한다고 하면

• A^11 = A^5 * A^5 * A
• A^5는 다시 A^2 * A^2 * A
• 이런 식으로 계속 반으로 쪼개며 올라온다.

즉, 곱셈 횟수가 11번이 아니라

log2(11) 수준으로 줄어든다.

---

7. 결론: 1629는 “빠른 거듭제곱 + 모듈러” 문제다

이 문제는 단순히 곱셈을 구현하는 문제가 아니라,

1. B가 매우 큰 상황에서
2. (A^B) % C를 효율적으로 계산하는
3. 분할정복(빠른 거듭제곱) 문제다.

• 단순 재귀/반복으로 B번 곱하면: 스택/시간 모두 터짐
• 지수를 반으로 쪼개면: O(log B) 로 통과
• 중간중간 % C를 적용해야: 오버플로우 없이 정확한 결과 유지