[알고리즘] 백준 1629 - 곱셈

문제 본문

문제 해설

곱셈이라는 문제는 A의 수를 B번 거듭제곱하여 C로 나눈 값을 반환하는 문제입니다.
보통 N의 알고리즘인 재귀 호출로 구하는 방법이 가장 쉽지만 A, B, C의 입력 범위가 장난 아니게 큽니다.

1 <= A,B,C <= 2,147,483,647

알고리즘의 수행시간 예측으로 1억 번의 연산이 1초 정도로 계산됩니다. 하지만 입력 범위가 최대 21억으로 N의 알고리즘을 수행한다면 문제에서 주어진 2초의 시간을 훨씬 넘을 것입니다. 이때 logN의 분할정복을 사용할 수 있습니다.

분할 정복은 문제의 범위를 2개 이상으로 잘게 쪼개어 계산하고 필요하다면 합치는 알고리즘입니다. 문제에서 주어진 거듭제곱은 수학에서 다음과 같이 표현할 수 있습니다. 2^12 = 2^6 * 2^6 , 2^6 = 2^3 * 2^3 즉 매번 계산하고자 하는 거듭제곱의 수식을 2개의 수식으로 나누어 계산하면 됩니다.

중요한 포인트만 몇 가지 적어두고, 총코드를 보여주며 이번 포스팅은 마치겠습니다.

 

변수의 정수 자료형

입력의 최대 범위가 21억이고 그 수의 곱셈의 결과까지 저장해야 하는 상황입니다. int의 최대 범위가 -21억 < int < 21억이지만 곱셈을 진행한다 했을 때 값을 저장하기에는 무리가 있습니다. 따라서 long 자료형을 사용해야합니다.

long 범위 -9223372036854775808 ~ 9223372036854775807

어랏 난 분명 분할 정복을 했는데?

  public static long division(long a, long b, long c) {
        if (b == 1) {
            return a % c;
        } else if (b % 2 == 0) {
            return (division(a, b / 2, c) * division(a, b / 2, c)) % c;
        } 

        ...(생략)...

위의 코드는 재귀 호출로 문제의 범위를 반으로 쪼개는 것으로 보이지만 결과적으로 같은 division 재귀를 2번 하는 꼴입니다. 문제와 같이 문제 범위에 따라 상황이 달라지거나, 정보가 달라지지 않는 이상 불필요한 호출로 이어지고 longN이 아닌 N의 알고리즘 수행 시간을 가지게 됩니다.

 

총 코드

import java.util.Scanner;

public class Main {

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

        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long c = scanner.nextLong();

        System.out.println(division(a, b, c));
    }

    public static long division(long a, long b, long c) {
        if (b == 1) {
            return a % c;
        } else if (b % 2 == 0) {
            long answer = division(a, b / 2, c);

            return (answer * answer) % c;
        } else {
            long answer = division(a, b / 2, c);

            return ((answer * answer % c) * a) % c;
        }
    }
}