Algorithm/acmicpc.net

분할 정복은 재귀인가? (#1629번 곱셈)

winney916 2022. 3. 24. 23:58
728x90

#1629번 곱셈 https://www.acmicpc.net/problem/1629

 

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

www.acmicpc.net

 

거듭제곱을 해결하는 문제인데, 자료구조 수업에서 다룬 적이 있던 것 같다.

 

틀린 코드

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


def fpow(C, n):
    if n == 1:
        return C
    else:
        x = fpow(C, n//2)
        if n % 2 == 0:
            return x * x
        else:
            return x*x*C


print(fpow(a, b) % c)

단순히 분할정복을 있는 그대로 구현했다. 하지만 시간초과가 나서 당황했다.

 

 

정답 코드

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


def fpow(C, n, z):
    if n == 1:
        return C % z
    else:
        x = fpow(C, n//2, z)
        if n % 2 == 0:
            return x * x % z
        else:
            return x*x*C % z


print(fpow(a, b, c))

문제에서는 정답을 c라는 수로 나눈 나머지만 구하는건데 이를 모든 연산에 적용했을 때 시간초과가 발생하지 않는다.

 

마지막에 도출된 큰 수에 나머지 함수를 적용하면 시간초과가 난다.

 

이유는..?

 

많은 자료를 찾아봤지만 만족스러운(충분히 납득할만한) 답을 얻지 못했다. 

아무튼 수가 커질수록 굉장히 오래걸린다는 점은 확실하다.