[코딩테스트] 곱셈 (분할 정복 알고리즘)

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

10 11 12

예제 출력 1

4

생각

• 처음에는 너무 간단하다고 생각했다 하지만 A,B,C의 범위를 보고 시간 초과가 날 것 같다는 생각이 들었지만 그래도 일단 시도해보았다

public int getRemain(int A, int B, int C) {

    int answer = 1;
    for (int i = 0; i < B; i++) {
        answer = answer * A % C;
    }
    return answer;
}

• 역시 시간 초과가 났다. B가 너무 클 경우 지나치게 많은 반복문이 돌아 시간 초과가 발생할 것이라고 생각했다. A^B에서 B가 클 경우 숫자가 너무 커지기 때문이다

• 그래서 복잡도를 줄여보기 위해 분할 정복 알고리즘을 도입하였다
  

코드

import java.util.Scanner;

public class Multiplication {

    public int getRemain(int A, int B, int C) {
        if (B == 0)
            return 1;  // A^0 = 1

        long half = getRemain(A, B / 2, C);
        long temp = half * half % C;

        if (B % 2 == 0)
            return (int) temp;
        else {
            return (int) ((temp * A) % C);
        }
    }

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

        int A = kb.nextInt();
        int B = kb.nextInt();
        int C = kb.nextInt();

        System.out.println(T.getRemain(A, B, C));
        kb.close();
    }
}

정리

분할 정복 알고리즘(Divide and Conquer)

• 큰 문제를 더 작은 문제로 나누어 (분할) 해결한(정복) 다음, 그 해결 방식을 합쳐서 전체 문제의 해답을 얻는 방식
• 재귀적으로 문제를 해결할 수 있는 경우 유용
• 예시: 병합 정렬(배열을 반으로 나누어 각각 정렬한 뒤 병합), 퀵 정렬(피봇 기준 배열을 두 부분으로 나누어 재귀적으로 정렬), 이진 탐색, 거듭제곱 계산

문제 출처