[Baekjoon] 1629번: 곱셈 - Java

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

1629번: 곱셈

문제 설명

A, B, C가 주어지면 A를 B번 곱한 후 C로 나눈 나머지를 출력해야 한다.

풀이 방법 1. 단순 계산 - 실패

문제를 보자마자 이 방법을 시도했고 바로 실패했다.

Math.pow(A, B) % C

카테고리가 분할 정복에 들어있는 것을 보았다.

일반적인 거듭제곱은 O(n)이지만 이를 분할 정복으로 바꾸면 O(n log n)이 된다.

거듭제곱을 분할 정복으로 해결하는 방법은 다음과 같다.

예를 들어 2^4 % 3을 한다고 하자. 2^4는 ( 2^2 ) * ( 2^2 ) 가 된다. 이는 또 ( 2^1 * 2^1 ) * ( 2^1 * 2^1 ) 가 된다. 이런 식으로 분할한 뒤 합치면 원하는 결과를 얻을 수 있다.

지수가 홀수라도 똑같은 방식이 가능하다.

2^5 를 나누면 2^4 * 2 가 된다. 결과적으로 ( 2^1 * 2^1 ) * ( 2^1 * 2^1 ) * 2 가 되는 것이다.

풀이 방법 2. 분할 정복 적용 - 실패

public static void main(String[] args) throws IOException {
    // ...
    
    System.out.println(pow(A, B) % C);
}

public static long pow(long x, long n) {
    if (n == 1)
        return x;
    long tmp = pow(x, n / 2);
    if (n % 2 == 0)
        return tmp * tmp;
    else
        return x * tmp * tmp;
}

이 방법도 실패하여 왜 그런지 생각을 해 보았다. 그 답은 금방 찾을 수 있었다. 문제에서 주어진 A, B, C의 각 범위는 2,147,483,647(2^31) 이하의 자연수다. 만약 A와 B가 상당히 큰 수라면 그 범위는 long의 양수 범위인 (2^64) - 1 의 범위를 벗어나게 된다. 그래서 자바에서 제공하는 BigInteger를 활용해 해결하려 했다.

풀이 방법 3. BigInteger 적용 - 실패(메모리 초과)

public static void main(String[] args) throws IOException {
    // ...
    
    System.out.println(pow(A, B).mod(C).intValue());
}

public static BigInteger pow(BigInteger x, BigInteger n) {
    if (n.compareTo(BigInteger.ONE) == 0)
        return x;
    BigInteger tmp = pow(x, n.divide(BigInteger.TWO));
    if (n.mod(BigInteger.TWO).compareTo(BigInteger.ZERO) == 0)
        return tmp.multiply(tmp);
    else
        return x.multiply(tmp).multiply(tmp);
}

이렇게 해도 실패해서 뭔가 다른 수학적인 방법이 있으리라 생각하고 구글링을 해보았고 역시나 있었다.

풀이 방법 4. 모듈러 합동 공식 적용 - 성공

참고한 글을 다음이다. https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - JAVA [자바]

이 문제에서 사용한 모듈러 합동 공식은 다음과 같다.

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

이를 분할 정복 함수에 적용하면 해결된다.

public static long pow(long x, long n) {
    if (n == 1)
        return x % C;

    long tmp = pow(x, n / 2);

    if (n % 2 == 0)
        return tmp * tmp % C;
    else
        return (tmp * tmp % C) * x % C;
}

전체 코드는 다음과 같다.

package baekjoon.dac;

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

public class BOJ1629 {

    static long C;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            long[] line =
                    Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
            long A = line[0], B = line[1];
            C = line[2];

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

    public static long pow(long x, long n) {
        if (n == 1)
            return x % C;

        long tmp = pow(x, n / 2);

        if (n % 2 == 0)
            return tmp * tmp % C;
        else
            return (tmp * tmp % C) * x % C;
    }
}

이번 문제를 통해 분할 정복 알고리즘을 다시 복기하고 모듈러 합동 공식을 알게 되었다. 간단해 보이는 문제도 규칙을 찾는다면 더 효율적인 방법으로 해결할 수 있다는 것을 다시 한 번 깨달았다.