[백준][분할 정복] 1629 곱셈 c++구현

목차

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

1629번: 곱셈

문제

 

문제 풀이 시 신경써야 할 점

• 시간 복잡도 -> 범위가 굉장히 넓기 때문에 for문을 쓸 경우 시간초과가 난다.

따라서 분할 정복을 통해 시간 복잡도는 O(logN)을 만들어 주어야 한다.

 

• int형 범위 -> int형 보다 훨씬 크기 때문에 long long int를 써주어야 한다

(a+b) % c = a%c + b%c

(axb) % c = a%c x b%c

수학적 원리를 잘 이용해 초과를 막아야한다.

 

코드 구현

#include <iostream>
#include<vector>
#include<algorithm>



using namespace std;
long long  int A, B, C, ret;
long long int multiply(long long int A, long long int B) {

	if (B == 1)
		return A%C;
	ret = multiply(A, B/2) % C;
	ret = (ret * ret) % C;
	if (B % 2)
		ret = (ret * A) % C;
	return ret;

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> A >> B >> C;
	cout << multiply(A, B)<<"\n";
	
}

 

재귀에 대한 이해가 필요하므로 나중에 다시 풀어보면 좋을 것 같다..