[백준] 1629 곱셈 python

www.acmicpc.net/problem/1629

1629번: 곱셈

# 분할정복
import sys; input = sys.stdin.readline
a, b, c = map(int, input().split())
def divNconq(a, b, c):
    if b == 1:
        return a % c
    tmp_a = divNconq(a, b // 2, c)
    return a * tmp_a * tmp_a % c if b & 1 else tmp_a * tmp_a % c
print(divNconq(a,b,c))

분할정복문제이다

dp방식으로 해보려했으나 메모리 초과로 많이 실패했다