[Python] 백준 1629번: 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

import sys
input = sys.stdin.readline


def getRemainderRecursively(curB):
    if curB == 1:
        return a % c

    halfRemainder = getRemainderRecursively(curB//2)
    toReturn = halfRemainder*halfRemainder
    if curB % 2 != 0:
        toReturn *= a

    return toReturn % c


if __name__ == '__main__':
    a, b, c = map(int, input().split())
    print(getRemainderRecursively(b))

분할정복을 통해 문제를 해결한다. 아래 사진을 보자.

10^11의 나머지를 구하기 위해선, (10^5) * (10^5) * 15가 필요하다는 뜻이다. 또한 홀수일 때는 a의 값을 1번 더 곱해줘야한다는 것을 유의하자.

아무튼, 위 사진처럼 분할정복을 하면, log(N)의 시간이 소요된다. 일반적인 방식으로, 무턱대고 10^11의 연산을 하려면 11번의 연산이 필요한데, 분할정복을 이용하면, 재귀함수를 11 -> 5 -> 2 -> 1에 대해서만 돌아주면 끝이 난다. 여기서 중요한 것은, 현재 숫자의 절반에 해당하는 값을 함수를 통해 1번만 구하고, 이 정보를 적절히 사용한다는 것이다. 즉, 11을 6, 5로 나눈 것은 재귀함수가 2번 들어가서 분할정복의 의의가 없어지고, 5, 5, 1로 나누게 되면 5에 대해서 재귀를 1번만 돌아도 되어 시간복잡도의 이득을 취한다는 것이다.

그리고 return값에 %c를 해주는데, 만약 %c를 해주지 않고, 얻은 최종값에 %c를 해주게 되면 값이 너무나도 커지게 된다. 따라서 미리 나머지를 구해주는 것이다.