티스토리 뷰

http://jason9319.tistory.com/169


예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다.


우선 소스코드를 먼저 보시죠


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, c;
ll mypow(ll x, ll y) {
    if (!y)return 1;
    if (y % 2)
        return (x*mypow(x, y - 1)) % c;
    return mypow((x * x) % c, y / 2) % c;
}
int main() {
    scanf("%lld%lld%lld"&a, &b, &c);
    printf("%lld", mypow(a, b));
    return 0;
}
cs


다음 소스코드는 BOJ 1629 곱셈 정답 소스코드입니다.


재귀 호출되는 과정을 보면 y가 홀수일 때는 brute force와 같은 직접 곱해주는 방법을 사용합니다.


하지만 y가 짝수일 때 y를 2로 나누어주면서 x를 제곱한 수를 호출합니다.


이와같은 분할정복으로 pow(a,b)를 logb 시간에 해결해줄 수 있습니다.

TAG
댓글
댓글쓰기 폼