[백준/C,C++] 1629번: 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

A의 B제곱을 C로 나눈 나머지를 구하는 문제인데, 그 수가 매우 클 수 있어 분할 정복을 이용해서 풀어야 하는 간단한 문제입니다.

 

 

힌트를 먼저 간단히 드리자면..

$A^{B}$ 과 같은 수식이 있을 때, B가 짝수라면,

$A^{B/2}\times A^{B/2}$ 으로 나타낼 수 있을 겁니다.

홀수라면, $A^{B/2}\times A^{B/2+1}$ 으로 나타낼 수 있겠죠.

 

 

문제와 달리 입력값이 작다고 예를 들어봅시다!!

 

만약 B가 10이라고 치면 A의 B제곱을 구할 때 일반적인 방법으로 아래와 같은 코드를 사용할 수 있을 겁니다.

 

#include<iostream>

using namespace std;

long long power(int A, int B)
{
	int res = 1;

	for (int i = 0; i < B; i++) {
		res *= A;
	}

	return res;
}

int main(void)
{
	int A = 2;
	int B = 10;

	cout << power(A, B);

	return 0;
}

 

하지만.. B가 굉장히 큰 수라면, 시간이 되게 오래 걸리게 됩니다.

 

시간 복잡도는 대게 for문에 의해 많이 좌우되기 때문이죠.

문제에서 B는 최대 2,147,483,647의 자연수로 주어진다고 합니다.

B의 값만큼 for문이 돌아가게 되니 B가 최대로 주어질 때 많은 시간이 걸리게 됩니다.

 

 

위에서 $A^{B}$ 는 $A^{B/2}\times A^{B/2}$ 또는 $A^{B/2}\times A^{B/2+1}$으로 나타낼 수 있다고 했습니다.

 

 

문제를 반으로 계속 줄이기만 해도 B의 최댓값인 약 21억이라는 수가 입력될 시에...

약 31번 만에 기저 사례까지 도달할 수 있습니다.

 

문제가 모두 분할되었으면 값을 계속 갱신해주면 되겠죠.

 

#include<iostream>

using namespace std;

long long power(int A, int B, int C)
{
    if (B == 1) return A % C;

    long long tmp = power(A, B / 2, C);

    return B % 2 ? (tmp * tmp % C) * A % C : tmp * tmp % C;
}

int main(void)
{
    long long A, B, C; cin >> A >> B >> C;

    cout << power(A, B, C) << endl;

    return 0;
}

 

해당 코드를 보시면 B값이 1이 될 때까지 계속해서 문제를 분할합니다.

 

B가 1이 되었을 때 A를 C로 나눈 나머지를 리턴합니다. 기저 사례인 거죠.

그 값은 함수를 호출했던 tmp에 담기게 되고 그 값을 제곱하여 다시 자신을 호출했던 함수의 tmp에 담기게 됩니다.