[코드업 2640] n의 k승 구하기 2

해당 문제는 단순히 동적계획법 패턴만으로는 메모리 초과가 발생하기 때문에 다른 방법을 사용했다. 분할과 정복 알고리즘을 사용하면 비교적 쉽게 풀 수 있다. 여기에 동적계획법을 적용하면 만족할 만한 실행속도도 확보할 수 있다.

 

#include <iostream>

using namespace std;

unsigned int cache[50000];

unsigned int mul(unsigned int n, unsigned int k) {
    if (k == 0) {
        return 1;
    }
    else if (k == 1) {
        return n;
    }
    else {
        unsigned int oddTrigger = 0;
        if (k % 2 == 1) oddTrigger = 1;

        unsigned long long left, right;

        if ((k / 2) + oddTrigger < 50000) {         
            if (cache[(k / 2) + oddTrigger]) {
                left = cache[(k / 2) + oddTrigger];
            }
            else {
                cache[(k / 2) + oddTrigger] = left = mul(n, (k / 2) + oddTrigger);    
            }
        }
        else {
            left = mul(n, (k / 2) + oddTrigger); 
        }

        if ((k / 2) < 50000) {
            if (cache[(k / 2)]) {
                right = cache[(k / 2)];
            }
            else {
                cache[(k / 2)] = right = mul(n, (k / 2));    
            }
        }
        else {
            right = mul(n, (k / 2));    
        }

        return (left * right) %  1000000007;
    }
}

int main() {

    unsigned int n, k;
    cin >> n >> k;
    cout << mul(n, k) << endl;

    return 0;
}
// 100000 100000000

 

사실 위의 코드도 최적화할 수 있는 방법이 많지만 우선 통과한 코드를 포스팅해본다. 독자 여러분들은 이미 최적화할 수 있는 방법을 찾았다고 생각한다!