[ 백준 ] 1629번 - 곱셈 (C++)

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

1629번: 곱셈

 

 

[ 문제풀이 ]

 

가장 기본적인 분할 정복 문제입니다. 제곱수의 값이 짝수이면 제곱수를 반으로 나누어 서로 곱하는 방식으로 진행하여 시간 복잡도를 O(logN)으로 줄일 수 있습니다. 시간을 더 단축하기 위해서 메모제이션을 해주어야 문제를 풀 수 있습니다.

 

[ 소스 코드 ]

#include<iostream>
#include<unordered_map>
 
#define ll long long
 
using namespace std;
 
ll A, B, C;
unordered_map<ll, ll> m;
 
ll conquer(ll num)
{
    if (num == 0) return 1;
    if (num == 1) return A % C;
    if (m[num] != 0) return m[num] % C;
 
    if (num % 2 == 0) {
        m[num] = conquer(num / 2) * conquer(num / 2);
        return m[num] % C;
    }
    else {
        m[num] = conquer(num - 1) * A;
        return m[num] % C;
    }
}
 
int main()
{
    scanf("%lld %lld %lld", &A, &B, &C);
 
    printf("%lld", conquer(B) % C);
}