1629번: 곱셈

문제

자연수 A를 B번 곱한 수를 구하려고 합니다. 단, 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 문제입니다.

• 입력: 첫째 줄에 A, B, C가 빈칸을 사이에 두고 주어집니다. (A, B, C는 모두 2,147,483,647 이하의 자연수)
• 출력: 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력합니다.

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

풀이

B가 최대 약 21억이므로 단순한 for 반복문(O(N))으로 A를 B번 곱하면 무조건 시간 초과가 발생합니다. 따라서 지수 법칙을 활용하여 연산 횟수를 절반씩 줄여나가는 분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring) 알고리즘을 사용해야 합니다. 시간 복잡도를 O(log N)으로 줄일 수 있습니다.

1. 지수 법칙과 분할 정복: A^B를 구할 때, 지수 B를 절반으로 나누어 계산합니다.
   • B가 짝수일 때: A^B = A^{B/2} * A^{B/2}
   • B가 홀수일 때: A^B = A^{B/2} * A^{B/2} * A 이를 재귀 함수 go로 구현하여 B가 1이 될 때까지 절반으로 나누며 파고듭니다.
2. 모듈로 연산의 분배 법칙: 숫자가 기하급수적으로 커지는 것을 막기 위해, 곱셈이 일어날 때마다 C로 나눈 나머지를 취해야 합니다. 모듈로 분배 법칙에 의해 (A * B) mod C = ((A mod C) * (B mod C)) mod C가 성립합니다.
3. 자료형 주의 (오버플로우 방지): 재귀 호출을 통해 반환된 tmp의 값은 최대 C - 1입니다. tmp * tmp를 계산하는 과정에서 (21억)^2에 가까운 값이 나올 수 있어 int형의 최댓값을 초과하게 됩니다. 따라서 이 곱셈 연산은 반드시 long 타입으로 형변환하여 수행한 뒤 모듈로 연산을 적용해야 합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int a = Integer.parseInt(st.nextToken());
       int b = Integer.parseInt(st.nextToken());
       int c = Integer.parseInt(st.nextToken());

       bw.write(go(a, b, c) + "");

       bw.flush();
       bw.close();
       br.close();
    }

    // 분할 정복을 이용한 거듭제곱 계산 메서드
    static int go(int a, int b, int c) {
       // 기저 조건: 지수가 1일 때는 a를 c로 나눈 나머지 반환
       if (b == 1) {
          return a % c;
       }

       // 지수를 절반으로 나누어 재귀 호출
       int tmp = go(a, b / 2, c);

       // tmp * tmp 과정에서 int 오버플로우가 발생할 수 있으므로 long으로 캐스팅 후 계산
       long ret = (long)tmp * tmp % c;
       
       // 지수가 홀수였다면 a를 한 번 더 곱해주고 모듈로 연산
       if (b % 2 == 1) {
          ret = (ret * a) % c;
       }
       
       return (int)ret;
    }
}

알고리즘 분류

수학 (Math), 분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring)