1629 곱셈

✏️ 문제

📝 풀이

A를 B번 곱하면 O(n)만큼 시간이 소요가 된다. 조건에서 A,B,C는 대략 21억 정도가 되니 시간제한 0.5초에 비하면 턱없이 오래 걸린다. 따라서, 분할 정복을 통해 시간 복잡도를 O(logn)으로 변경해야 한다.

시간복잡도를 어떻게 O(logn)으로 줄일 수 있을까?🤔

ex) B = 10일 때
일반적으로 n을 b만큼 곱한다면
func(10) = n * n * n * n * n * n * n * n * n * n
=> 총 10번 연산

ex) 분할 정복일 때
func(10)
= func(5) * func(5)
=> 1번

func(5)
= func(2) func(2) n
=> 2번

func(2)
= func(1) * func(1)
=> 3번

func(1)
= n
=> 총 4번 연산

시간복잡도는 해결했으나 큰 수를 곱하면 공간복잡도 측면에서 문제가 생기는데 어떻게 해결할 수 있을까?🤔

모듈러 성질 : (a*b)%c = (a%c * b%c)%c

📝 코드

for test_case in range(1):
    a, b, c = map(int, sys.stdin.readline().split())

    def dfs(b):
        if b == 1:
            return a % c
        if b % 2 != 0:
            num = dfs(b // 2)
            return ((num%c) * (num%c) * a)%c
        else:
            num = dfs(b // 2)
            return ((num%c) * (num%c))%c

    print(dfs(b))