[Algorithm/BOJ] 1629 곱셈 C++ : 분할정복

재귀 호출을 할 때 같은 값을 사용해야한다면 필요할 때마다 재귀호출을 하는 건 시간 / 메모리 측면에서 낭비...

=> 재귀 호출한 값을 저장해놓고 사용할 것

 

이 문제에서 가장 중요했던 것!

//b가 짝수이면 : a^b = a^(b/2) x a^(b/2)

//b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1)

요거이다

...

 

#include <iostream>
using namespace std;

long long a, b, c, tmp;

long long power(long long b) {
    if(b==0) return 1;
    if(b==1) return a%c;

    tmp=power(b/2)%c;
    if(b%2==0) return tmp*tmp%c;
    else return tmp*tmp%c*a%c;
}

int main(){
    cin >> a >> b >> c;
    cout <<power(b);
}

참고 : https://velog.io/@junttang/BOJ-1629-%EA%B3%B1%EC%85%88-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C