[SW Expert Academy] 1217번 C++ 풀이

Sw Expert Academy 1217 - [S/W 문제해결 기본] 4일차 - 거듭 제곱

SW Expert Academy

시간 제한	메모리 제한	난이도
(C++ 기준) TC 10개, 10초	힙, 정적 256MB, 스택 1MB	D3

 

문제 요약 : 거듭 제곱을 분할 정복으로 구현하라.

 

https://codejin.tistory.com/114

백준 1629번 C언어 풀이

 

이전에 풀었던 이 문제보다도 쉬운 문제였다. 결과값이 int의 범위를 넘어가지 않기 때문이다. 풀이 역시 위 문제에서 모듈러 연산만 제외하면 되니 위 글를 참조하자.

 

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

// a^b == a^(b/2) * a(b/2)
// 분할 정복으로 이를 구현한다.
int sol(int base, int exp) {
    if (exp == 0) return 1;
    if (exp == 1) return base;
    else {
        if (exp & 1) return base * sol(base, exp / 2) * sol(base, exp / 2); 
        else return sol(base, exp / 2) * sol(base, exp / 2);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("input.txt", "r", stdin);
    
    int test_case = 10;
    int T;
    int base, exp;

    while(test_case--) {
        cin >> T >> base >> exp;
        cout << "#" << T << " " << sol(base, exp) << endl;
    }

    return 0;
}