[Beakjoon] 백준 1629번 곱셈 (Java)

1629 곱셈

 

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

 

난이도 및 유형

난이도 : 실버 1

유형 :   재귀

시간제한 : 0.5초

메모리제한: 128MB

 

문제

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

입력

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

출력

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

 

 

문제풀이

이 문제는 주어진 입력값에서 확인할 수 있듯이 A를 B번 곱해야 한다. 하지만, B의 값이 int의 최대값이기 때문에 최악의 경우 A를 약 21억번 이상 곱해야 한다. 따라서, 시간초과가 발생할 수 있었다. 분할정복을 통해 문제를 해결해야 한다고 생각했지만 어떻게 해결해야 할지 감이 오지 않았다. 해결방법을 찾던 중 지수 법칙과 모듈러 법칙을 이용하면 제한시간을 만족해 문제를 해결할 수 있다는 힌트를 얻을 수 있었다. 

 

[지수 법칙]

a^m * a*n = a^m+n

 

[모듈러 법칙]

(a*b) mod c = (a mod c * b mod c) mod c

 

위 법칙들을 문제에서 활용하면 O(logN) 시간복잡도로 문제를 해결할 수 있다. 위의 법칙을 문제의 예제에 적용하기 전에 주의해야 할 점이 있다. 만약, 지수가 홀수라면 짝수 일때와 처리하는 방식을 다르게 해줘야 한다는 것이다. 

 

[지수가 홀수일 경우]

지수가 홀수라면 홀수를 2로 나누었을 때 남은 값을 연산에 추가해 지수를 맞추어 주어야 한다. 지수를 맞추는 이유는 연산의 반복을 줄여 계산 횟수를 줄일 수 있기 때문이다.

10¹¹ mod 12 = (10⁵ * 10⁶) mod 12 = ((10⁵ mod 12) * (10⁵ mod 12)) * 10¹ mod 12

 

[지수가 짝수일 경우]

10⁴ mod 12 = (10² * 10²) mod 12

 

이제 위의 규칙을 참고해서 예제를 살펴보자. 예제는 a = 10, b = 11, c = 12의 값이 주어진다. 즉, 10의 11제곱을 12로 나눈값을 구하면된다. 지수 법칙을 이용해 예제를 세분화 해보면 아래와 같다. 밑줄 친 부분을 중점적으로 살펴보면 규칙을 파악할 수 있다.

10^11mod 12
= ((10^5 mod 12) * (10^5 mod 12)) * 10 mod 12
= ((10^2 mod 12) * (10^2 mod 12)) * 10 mod 12
= ((10^1 mod 12) * (10^1 mod 12)) mod 12
= 10^1 mod 12

위 내용을 토대로 코드를 구현하면 아래 코드와 같다.

 

 

[정답코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        long a = Integer.parseInt(stringTokenizer.nextToken());
        long b = Integer.parseInt(stringTokenizer.nextToken());
        long c = Integer.parseInt(stringTokenizer.nextToken());

        System.out.println(calculate(a, b, c));
    } // main

    private static long calculate(long a, long b, long c) {
        if (b == 1) {
            return a % c;
        } // 지수가 1이면 나머지를 구한다.

	    // 지수가 1 이상이면 지수를 반으로 나눈 후 
        // 지수가 홀수일 때와 짝수일 때를 구분해 다시 나머지를 구한다.
        long result = calculate(a, b / 2, c);

        if (b % 2 == 1) {
            return result * result % c * a % c;
        } // 지수가 홀수일 때 나머지를 구하는 식

        return result * result % c;
    }
} // class