[백준_1629번] 곱셈

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

1629번: 곱셈

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1629 {
	public static long a,b,c;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		a=sc.nextLong();
		b=sc.nextLong();
		c=sc.nextLong();
		
		System.out.println(pow(a,b));
	}
	
	/*
	 * 지수를 반으로 나누는 과저을 지수가 1일 떄 까지 반복한다.
	 * 예를 들어 10^11인 경우는
	 * 10^5 * 10^5 * 10^1로 나눌 수 있고, 10^5를 또 나누면
	 * 10^2 * 10^2 * 10^1, 10^2를 또 나누면
	 * 10^1 * 10^1이 된다.
	 * 
	 * 이러한 과정에서 지수는 절반으로 나뉘기 때문에 각 단계에서 나뉜
	 * 두 지수를 모두 계산할 필요 없이 한 번만 구하면 된다.
	 */
	public static long pow(long a, long exponent) {
		// 지수가 1인 경우 a^1 이므로 a 리턴
		if(exponent==1)
			return a%c;
		
		// 지수의 절반에 해당하는 값을 구한다.
		long temp=pow(a,exponent/2);
		
		/*
		 * <모듈러 합동 공식> : (a * b) % C = ((a % C)*(b % C)) % C
		 * (temp * temp * A) % C 
		 * = ((temp * temp % C) * (A % C)) % C
		 * = (((temp * temp % C) % C) * (A % C)) % C
		 * = ((temp * temp % C) * A) % C
		 * 
		 * 이때 지수가 홀수가 될 경우는 
		 * A^(exponent / 2) * A^(exponent / 2) * A 이므로
		 * A를 한 번 더 곱해주어야 한다.
		 * 
		 * ex) A^9 = A^4 * A^4 * A
		 */
		if(exponent%2==1)
			// (temp*temp*a)%c를 변환한 식
			return (temp*temp%c)*a%c;
		
		/*
		 * 지수가 짝수인 경우에는
		 * 구했던 값을 한번 더 곱한 뒤 c 값을 나눠 반환
		 */
		return temp*temp%c;
	}
}

[고찰]

 이번 문제는 시간초과로 인해 분할 정복과 모듈러 합동 공식을 반드시 사용해야 하는 문제였다. 이에 대한 해답이 나오지 않아 다른 사람의 포스팅을 참고하여 이해하고, 문제를 해결하였다.

우선 해당 문제에서 분할 정복을 활용하는 방법은 지수가 1이 될 때 까지 지수를 반으로 나누는 작업을 계속하는 것이다. 이때 각 단계에서 지수는 같은 값으로 /2 되기 때문에 두 지수를 모두 탐색할 필요가 없다. 

또한 (a * b) % C = ((a % C)*(b % C)) % C와 같은 모듈러 합동 공식을 사용하여 c로 나눈 나머지를 구해야 한다. 그 이유는 temp*temp*a%c 그대로 계산하게 되면 long 형의 범위를 넘어가기 때문이다.

 이러한 해결 방법을 스스로 생각해내지 못했다. 이처럼 모듈러 공식이나 지수의 성질을 사용하여 해결하는 문제들을 좀 더 접해봐야겠다.