[파이썬] 1629번. 곱셈 풀이

이 문제의 분류는 "분할 정복을 이용한 거듭제곱" 이다.

즉, 어떤 수를 매우 큰 횟수로 거듭제곱 한다면, 시간복잡도를 줄이는 방법을 묻는 문제인 것이다.

 

예를 들어, 2를 32번 제곱한다는 것은 -> (2^16)^2, 즉 2의 16승을 한 번 제곱한 값과 같다.

                 그러면 32번의 연산에서 -> 17번의 연산으로 감소한다!

더 나아가서 ((2^8)^2)^2) 는 10번의 연산만 요구한다. (((2^4)^2)^2)^2)는 단 7번의 연산만 요구한다!

 

---

def reduce_pow(a, b, c):
    if (b == 1):
        return a % c

    X = reduce_pow(a, b//2, c)

    if (b % 2 == 0): # 짝수라면
        return X * X % c
    else: # 홀수라면
        return a * X * X % c

A, B, C = map(int, input().split())

print(reduce_pow(A, B, C))

 

1) b가 1이면 a 값이 그대로니까, a % c를 반환한다.

 

2) b 값이 2 이상부터는 거듭제곱하는 횟수(b)를 절반씩 줄여 재귀한 값을 X에 담는다.

    예를 들어, a가 2, b가 4라면 2 ^ 4 = 16이다.  그러면 2^2 인 4(X)를 다시 제곱하면 똑같이 16이 나온다.

    반대로, a가 2, b가 5라면 2 ^ 5 = 32니까 2^2인 4(X)를 다시 제곱하고, 그 값에 다시 a를 곱하면 32가 나오게 된다.

 

3) 따라서, 현재 단계의 거듭제곱하는 횟수(b) 값이 짝수라면 그대로 (X * X) % c 값을 반환하고,

    홀수라면 (a * (X * X)) % c 값을 반환하면 된다!