[C++]백준1629번 곱셈

오늘은 백준1629번 곱셈 문제를 풀어보도록 하자. 문제는 되게 간단하다 (문제만). 만일 하나하나 계산한다면

O(N)으로 시간제한 0.5초를 무조건 넘기게 된다. 하지만 분할정복 알고리즘을 이용하면 O(logN)으로 시간복잡도는 확 줄게 된다.

따라서 위 문제는 분할정복으로 풀어야한다..

데이터 범위가 21억으로 int범위 끝까지 갈 수 있고 곱셈이기 때문에 long long 타입으로 잡아줘야한다. 그리고 long long으로 잡아도

터질 수 있으므로 modulation연산을 적재적소에 해줘야 한다.

문제는 다음과 같다.

                               [접근법]

  1. 생각을 해보자. 만일 2^16이 있다면 2를 16번 곱하는 것보다 2^8을 2번 곱하는 것이 빠를 것이다. 이런 아이디어를 이용하여 재귀적으로 풀어가는 것이 분할정복이다.
  
  2. 2로 계속 나눠주면서 제곱을 해주고 modulation연산을 해준다.

  3. 마지막에 만일 B가 홀수였다면 A을 한 번 더 곱해주는 것을 잊지 말자.(물론 modulation 연산도 잊지 말아야 한다.)

                                     [코드]
#include <iostream>
using namespace std;

long long calculation(long long A, long long B, long long C) {
	if (B == 0) {
		return 1;
	}
	long long result = calculation(A, B / 2, C);
	result = result * result % C;

	if (B % 2 == 0) {
		return result;
	}
	else {
		return (result * A) % C;
	}
}

int main() {
	long long A, B, C;

	cin >> A >> B >> C;

	cout << calculation(A, B, C) << '\n';
	return 0;
}