[백준][C++] 1629번: 곱셈 <187>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1629번: 곱셈

생각의 흐름

입력으로 받을 A, B, C 모두 int형으로 담을수 있는 값이다.

 

하지만 A^B를 한다 했을때, 이를 직접 계산하려면

1) 변수 크기도 엄청 커지게 된다.

2) 자료의 크기 1억당 => 1초 정도 걸리기 때문에, 2^2,147,483,647 만 계산하려 해도 21초나 걸린다.

 

따라서 이를 분할정복으로 해결해야 한다.

 

예를들어 2^8을 구해야 핸다고 해보자.

이는 2^4를 구해 2번 구하면 된다. 한번만 2^4를 구하면 두번째 2^4는 계산할 필요가 없다.

다시 2^4를 구할때는 2^2를 2개 구하면 된다.

이런식으로 분할정복 해가면, 시간 또한 O(logN) 시간안에 가능하다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

int A, B, C;

long long pow(int num, int exponent){
    if(exponent == 0){
        return 1;
    }else if(exponent == 1){
        return num;
    }
    if(exponent % 2 > 0){
        return pow(num, exponent-1) * num;
    }

    long long half = pow(num, exponent/2) % C;
    return (half * half) % C;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> A >> B >> C;

    long long int res = pow(A % C, B);
    cout << res % C;
    return 0;
}