[백준 1629] 곱셈

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll go(ll a, ll b){
    if(b==1)
        return a % c;
    ll _c = go(a, b/2);
    _c = (_c * _c) % c;
    if(b % 2)
        _c=(_c * a) % c;
    return _c;
}

int main(){
    cin >> a >> b >> c;
    cout << go(a,b) << "\n";
    return 0;
}

 

시간 제한이 0.5초이기 때문에 일반적인 제곱 방식으로 접근하면 시간 초과가 나기 쉬운 문제다...

a를 b번 곱하는 (b 제곱)하는 수가 결국 반복되는 과정이기 때문에 분할정복 알고리즘에 해당하며 메모이제이션 방법을 사용했다

 

분할정복(Divide and Conquer) 알고리즘이란?

주어진 문제를 작은 사례로 나누고 (Divide) 각각의 작은 문제들을 해결하여 정복(Conquer) 하는 방법이다

 

위 문제 같은 경우에는

ll go(ll a, ll b){
    // Divide: 문제가 분할이 가능할 경우 2개 이상의 문제로 나눈다
    // Conquer: 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행하며 그렇지 않으면 문제를 푼다.
    if(b==1)
        return a % c;
    ll _c = go(a, b/2);
    
    // Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.
    _c = (_c * _c) % c;
    if(b%2)
        _c=(_c * a) % c;
    return _c;
}

 

일반적으로 문제를 푼다면 큰 값 (제곱이기 때문에 값이 큼...)을 계속해서 제곱해주기 때문에 시간초과가 날 수 밖에 없다

제곱해주는 값을 지수의 법칙을 이용하여 분할(Divide)이 가능할 때까지 지수를 반으로 나눠주고 이를 재귀로 구현하였다

 

유명한 메모이제이션 문제...