[실버 1] 백준 1629 - 곱셈 (파이썬)

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

풀이

• A^B % C를 직접 계산하면 시간 복잡도 O(B), 너무 크다.
• A^B = A^(B//2) * A^(B//2) (짝수일 경우)
• A^B = A^(B//2) * A^(B//2) * A (홀수일 경우)
• 이를 이용해서 재귀적으로 절반씩 계산하면서 나머지를 구하는 방식을 사용한다. → 시간복잡도 O(log B)

def power(a, b, c):
    if b == 0:
        return 1  # a^0 = 1
    if b == 1:
        return a % c  # a^1 % c = a % c
    
    x = power(a, b // 2, c)  # A^(B//2) 값을 재귀 호출로 구함

    if b % 2 == 0:
        return (x * x) % c  # A^B = x^2 if B is even
    else:
        return (x * x * a) % c  # A^B = x^2 * a if B is odd

• 재귀적으로 power(a, b // 2, c) 를 호출함으로써 log₂(b) 번만 연산한다.
• 각 단계마다 곱셈을 하고 나머지 연산 % c 를 하기 때문에 숫자가 커져도 오버플로우 없이 처리 가능하다.

코드

# 백준 1629 - 곱셈
# 분류 : 다이나믹 프로그래밍

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

def power(a, b, c):
    if b == 0:
        return 1
    if b == 1:
        return a % c
    
    x = power(a, b // 2, c)
    if b % 2 == 0:
        return (x * x) % c
    else:
        return (x * x * a) % c

print(power(A, B, C))