[백준-1629] 곱셈

1629번: 곱셈

 

 

시간복잡도를 먼저 봐야하는 문제이다.

0.5초의 시간제한에 2147483647 이하의 입력값에 직접 모든 계산을 돌린다면 엄청난 차이로 시간이 터지게 된다. 때문에 log(n) 이하의 알고리즘을 생각해야 한다.

log 를 보자마자 절반으로 나눠볼까? 라는 생각을 한 뒤 분할하여 값을 구하면 되지 않을까 생각이 든다. 즉 다음과 같은 로직으로 코드를 짤 수 있다.

1. 제곱수를 절반으로 쪼개 분할정복

2. 틀 만든 뒤 return (?!)

생각보다 간단하게 끝난다. 다만 계산 중간 곱한 뒤 나누는 과정에서 int 의 범위를 벗어날 수 있기 때문에 long long 으로 처리해주어야 한다.

 

#include <iostream>

using namespace std;
typedef long long LL

LL _get(LL x, LL y, LL z) {
	if (y == 1) return x % z;
	else {
		LL half = _get(x, y / 2, z);
		if (y % 2 == 0) {
			return (half * half) % z;
		}
		else {
			return (x * ((half * half) % z)) % z;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	LL a, b, c;
	cin >> a >> b >> c;

	cout << _get(a, b, c);
	return 0;
}