[알고리즘] 분할정복 - 백준 1629번 곱셈

첫 번째 시도 : 시간 초과 (런타임 오류)

A, B, C = list(map(int, input().split(' ')))

def solution(A):
    global B

    if B == 1:
        return A
    else:
        B -= 1
        return solution(A) * A

print(solution(A) % C)

두 번째 시도 : 성공

A, B, C = list(map(int, input().split(' ')))

def solution(A, B):
    if B == 1:
        return A % C
    else:
        value = solution(A, B//2)
        if B % 2 == 0:
            return value * value % C
        else:
            return value * value * A % C

print(solution(A, B))

풀이과정

10^11 % 12 를 구해야 한다고 가정해보자.
첫 번째 시도의 방법은 10 * 10 * ... * 10 처럼 10을 있는 그대로 11번 곱하는 방법이다. 하지만, 곱하는 수가 커지면 런타임 오류가 발생한다.
따라서 최대한 곱하는 수를 줄여줘야 한다. (10^5)*(10^5) 이렇게 두 개로 나눠주면 시간이 반으로 줄어든다.

세 번째 시도 : 성공

A, B, C = list(map(int, input().split(' ')))

print(pow(A, B, C))

파이썬에서는 pow 함수를 제공한다.
pow(A, B, C) = A^B % C 를 의미한다. 복잡한 과정없이 함수를 통해 한 방에 해결할 수 있는 문제였다.