백준 1629번: 곱셈 [python]

https://www.acmicpc.net/problem/1629

문제 접근

문제 자체는 심플한데 그냥 곱하고 나누면 시간초과가 난다.

분할 정복을 이용한 거듭제곱 기법 을 써야한다.

무엇이냐 하면 2의 32승을 계산할때 2를 32번 곱해야하지만 2의 16승의 제곱을 해도 된다. 즉 2의 16승까지만 계산하면 17,18..32를 계산안해도 된다는 의미이다.

B가 1이라면 바로 C를 리턴해주고
B가 홀수라면 제곱에 a를 한번 더 곱해주는것으로 처리한다.

풀이 및 해답

import sys
input = sys.stdin.readline

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

# 분할 정복 함수 정의
def power(a, b):
    # base case: b가 1이면 a % C 리턴
    if b == 1:
        return a % C
    
    # b를 반으로 나눈 값을 재귀 호출
    half = power(a, b // 2)

    # b가 짝수면 half * half
    if b % 2 == 0:
        return (half * half) % C
    # b가 홀수면 half * half * a
    else:
        return (half * half * a) % C

print(power(A, B))