[백준 C++] 1629 곱셈 - 분할정복

1629번: 곱셈

#include <iostream>
using namespace std;

int A, C;

long long BinaryFunction(int B)
{
	if (B == 0)
	{
		return 1;
	}
	else if (B == 1)
	{
		return A % C;
	}

	if (B % 2 == 0)
	{
		return BinaryFunction(B / 2) * BinaryFunction(B / 2) % C;
	}
	else
	{
		return BinaryFunction(B / 2) * BinaryFunction(B / 2 + 1) % C;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int B;
	cin >> A >> B >> C;

	cout << BinaryFunction(B);
}

---

 

재귀 함수를 이용해서 푸는 분할 정복 유형의 문제입니다.

 

결론적으로 A를 B번 곱한 값을 출력해야 하는데,

곱하는 도중에 값이 자료형의 범위를 넘어갈 수 있기 때문에

매번 곱할 때마다 C로 나눈 나머지 값으로 갱신해주어야 합니다.

그리고 그냥 순차적으로 반복하게 되면 O(N)의 시간 복잡도로 시간 초과가 발생할 수 있습니다.

따라서 A^B = A^(B1) * A^(B2)의 성질(B = B1 + B2)을 이용해서 재귀 함수O(logN)로 풀어야 합니다.

 

B가 짝수일 경우: A^B = A^(B/2) * A^(B/2),

B가 홀수일 경우: A^B = A^(B/2) * A^(B/2 + 1)