곱셈 By 분할정복

백준 1629번: 곱셈

아이디어

a를 b번 곱하는 대신 b/2번 곱한걸 제곱하면 연산 횟수를 줄일 수 있다. b가 1이 될 때까지 반복한다. 곱셈 연산을 21억번 하면 0.5초 안에 끝낼 수 없지만 이 방법을 사용하면 O(logN)의 시간복잡도를 가지기 때문에 0.5초 안에 끝낼 수 있다.

코드

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

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

print(power(A, B, C))

여담

아이패드로 문제를 풀었는데 잘 풀려서 기분이 좋다. 앞으로 이걸로 열심히 문제를 풀어야겠다.
아이패드 프로 5세대 12.9인치 + 매직키보드 + 애플펜슬 = 190만원 아 ㅋㅋ