[백준 14731번] 謎紛芥索紀 (Large) (C++)

문제링크 : https://www.acmicpc.net/problem/14731

14731번: 謎紛芥索紀 (Large)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007

ll cal(ll a)
{
    if(a==0) return 1;
    ll half = cal(a/2);  //반으로 나눠주기
    if(a%2==1) return (half * half * 2) % MOD;  
    return (half * half) % MOD;    
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll N, C, K;
    ll result=0;
    cin >> N;
    while(N--)
    {
        cin >> C >> K;
        result += (((C*K)%MOD) * cal(K-1))%MOD;
    }
    cout << result%MOD;
    return 0;
}

단순히 거듭제곱으로 풀었다가 시간초과가 났던 문제다.

분할정복으로 풀어야했는데 분할정복 알고리즘을 적용을 거의 안해봐서 다시 따로 보고 풀었다.

거듭제곱수가 짝수일때는 각 수를 반으로 나눠주고, 그 반으로 나눠준 값을 제곱하여 반환해준다.

거듭제곱수가 홀수일때는 짝수횟수만큼 위의 과정을 반복하고, 마지막 1번은 위의 문제의 경우 2만 거듭제곱하므로 2를 마지막에 곱해준다.