Sw Expert Academy 1217 - [S/W 문제해결 기본] 4일차 - 거듭 제곱
시간 제한 | 메모리 제한 | 난이도 |
(C++ 기준) TC 10개, 10초 | 힙, 정적 256MB, 스택 1MB | D3 |
문제 요약 : 거듭 제곱을 분할 정복으로 구현하라.
https://codejin.tistory.com/114
이전에 풀었던 이 문제보다도 쉬운 문제였다. 결과값이 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;
}
'coding_test > SW Expert Academy' 카테고리의 다른 글
[SW Expert Academy] 1289번 C++ 풀이 (0) | 2023.02.05 |
---|---|
[SW Expert Academy] 10505번 C++ 풀이 (0) | 2023.02.05 |