백준 1629: 곱셈 (파이썬)

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

1629번: 곱셈

---

코드

# https://teching.tistory.com/

a, b, c = map(int, input().split())


def pastPow(a, b, c):
    if b == 0:
        return 1
    elif b == 1:
        return a % c
    else:
        DivCon = pastPow(a, b // 2, c)
        if b % 2 == 0:
            return (DivCon * DivCon) % c
        else:
            return (DivCon * DivCon * pastPow(a, 1, c)) % c

res = pastPow(a, b, c)
print(res)

해설

일반적인 재귀 방법으로 하면 당연스럽게도 시간 초과가 발생한다. 왜냐하면 O(n)의 시간이 걸리기 때문이다.

따라서 분할 정복을 사용해서 거듭제곱을 처리해야한다.

그러기 위해서는 거듭제곱을 먼저 이해해야 한다.

 

a의 n제곱이라 하면 a를 n번 제곱을 한 것이다.

따라서 이는 a^n = a*a*... *a (n번 곱함)으로 나타낼 수 있고 

n가 짝수일 경우에는 반씩 나누어서 a^n = a^(n/2) * a^(n/2)로 나타낼 수 있다.

홀수인 경우에는 짝수에서 a를 한 번 더 곱해주면 된다.

 

예를 들어 설명해보면 3^7을 구하기 위해서는

일반적인 방법으로는

3^7 = 3^6*3

...

3^3 = 3^2*3

3^2 = 3^1*3

3^1 = 3^0*3

3^0 = 1

이렇게 구해줘야 했다.

하지만 분할 정복의 방법으로 구해주면

n이 홀수인 3의 7 제곱(3^7)은 3^3 * 3^3 * 3으로 나타낼 수 있다.

또한 3^3 또한 홀수이기 때문에 3^3 = 3^1 * 3^1 * 3으로 나타낼 수 있다.

따라서 

3^7 = 3^3 * 3^3 * 3

3^3 = 3^1 * 3^1 * 3

3^1 = 3

이렇게 연산이 매우 적게 걸리게 된다.

이를 이용해서 계속 반씩 구하면 빠르고 쉽게 거듭제곱을 구할 수 있다.

이렇게 분할 정복을 사용해서 거듭제곱을 구하면 걸리는 시간은 O(log n)이 된다.

 

마지막으로 문제에서 조건으로 준 오버플로우를 방지하기 위해서 c로 나머지 연산을 하는 연산을 추가해주면 된다.