[백준/파이썬]1629번 곱셈

-코드

from sys import stdin
a, b, c = map(int, stdin.readline().split())


def sol(x, y):
    if y == 1:
        return a % c
    r = sol(x, y // 2)
    if y % 2 == 0:
        return r * r % c
    else:
        return r * r * x % c


print(sol(a, b))

친구가 분할 정복을 물어보니 풀어보라고 한 문제이다, 처음에는 그냥 제곱해서 나머지를 구하는 식을 사용하였으나 풀리지 않아서 dp를 사용해 풀어 보라고 해서 사용하여 풀어봤으나 메모리 초과가 계속 떠서 찾아보니 반복문을 이용한 dp라서 메모리 초과에서 걸렸다고 한다. 그래서 다른 방법을 찾아보니 이분 탐색과 비슷하게 계속 반복하여 가장 적은 횟수로 해결을 하도록 sol(x,y//2)를 이용하여 값이 나올 때까지 반복하여 해결하는 알고리즘으로 분할 정복도 많이 풀어봐야 겠다고 생각을 했다