백준 1629 - 곱셈(C++)

문제

자연수 A를 B번 곱하는 거듭제곱을 구하는 문제이다. 이때 구하려는 수가 커지는 것을 방지해 C를 나눈 나머지를 구하는 프로그램을 작성한다.

A^B

입력

A, B, C가 차례대로 주어진다.

 

입력 예제

10 11 12

예제 출력

4

문제 해결

어디서 힌트를 얻을 수 있을까?

 

문제에서는 A를 B번 곱한 수를 구하는 것이라고 했다. 이 말을 다르게 생각하면 A는 B의 거듭제곱이 되는 것이다.

 

거듭제곱은 수열의 빠른 합과 같은 맥락으로 풀 수 있다. 즉, B를 계속 반으로 나눈 값으로 문제를 푸는 것이다.

 

이렇게 된다면 문제는 다음과 같이 정의할 수 있다.

• A^(B/2) * A^(B/2)
  ↓
• K = A^(B/2)
  ↓
• K * K

위와 같이 바꿀 수 있는 것이다. 그러면 홀수의 경우는 어떨까? 홀수의 경우에는 다음과 같이 처리할 수 있다.

• A^(B - 1) * A

그럼 여기서 한 가지 의문이 들 수도 있다. 왜 홀수일 때도 반으로 나누지 않는 것일까? 홀수를 절반으로 나누게 된다면 중복되는 문제가 생기게 된다. 이러한 중복되는 반복 문제를 방지하기 위해서 홀수를 1로 빼서 짝수로 만든 것이다.

 

이렇게 되면 호출되는 부분 문제의 수는 증가할지는 몰라도 중복되는 부분 문제를 줄일 수 있어 실질적으로 효율적으로 만들 수 있는 것이다.

코드

#include <iostream>
#include <vector>

long long A, B, C;

long long power(long long X)
{
	if (X == 0)
		return 1;
	if (X == 1)
		return A % C;
	if (X % 2 != 0)
		return power(X - 1) * A % C;
	long long half = power(X / 2) % C;
	return ((half % C) * (half % C)) % C;

}

int main(void)
{
	std::cin >> A >> B >> C;
	std::cout << power(B) << std::endl;
	return 0;
}

문제 출처

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

1629번: 곱셈