(백준/C++) 1629_곱셈

1629번: 곱셈 (acmicpc.net) 문제도 분할 정복(Divide and Conquer)으로 풀어볼 수 있습니다.

분할 정복은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 합쳐 원래 문제의 해결책을 찾는 방법입니다.

이 문제는 A를 B번 곱할 때, 현존하는 자료형보다 커질 수 있기 때문에 C를 나눈 나머지를 사용합니다.

즉, $A^B\mod C$를 구해야 하는 문제입니다. 이때, 이 $A^B$를 분할 정복으로 계산하는 방법을 생각하게 되는 문제입니다.

---

접근법

분할 정복(Divide and Conquer)은 세 가지 접근법으로 먼저 생각해볼 수 있습니다.

바로, 분할 - 정복 - 결합 입니다.

1) 분할(Divide)

이 문제는 $A^B$를 분할 정복으로 계산해야 합니다. 이를 더 작은 문제로 나눌 때, $B$가 짝수일 경우와 홀수일 경우로 나누어 생각할 수 있습니다.

• $B$가 짝수일 때: $A^B=(A^{B/2})^2$
• $B$가 홀수일 때: $A^B=A×(A^{B-1/2})^2$

2) 정복(Conquer)

분할한 문제를 재귀적으로 해결합니다.

여기에서는 $A^{B/2}$ 나 $A^{(B-1)/2}$ 을 재귀적으로 호출해 나아갑니다.

기저 사례(Base Case): $B=0$ 일 때, $A^0=1$ 이므로 1을 반환합니다.

3) 결합(Combine)

분할한 문제의 해를 결합하여 원래 문제의 해를 구합니다.

---

풀이

#include <iostream>
#include <cmath>
using namespace std;

long long solve(long long A, long long B, long long C)
{
	if (!B) return 1;

	// A ^ B % C
	// B가 홀수: (A * A ^ (B-1/2))^2 % C
	// B가 짝수: (A ^ (B/2))^2 % C
	long long half = solve(A, B / 2, C);
	if (B & 1)
		return (half * half % C * A) % C;
	else
		return (half * half) % C;
}

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

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

	cout << solve(A, B, C);
}