[백준/Python] 1629번 곱셈

---

문제

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

---

문제 이해

문제 이해는 간단했다.

a를 b번 거듭제곱 한 후, 그 수를 c로 나눈 나머지 값을 출력하면 되는 간단한 문제라 생각했다.

 

하지만 시간초과의 벽에 부딪혔다...

---

문제 풀이(시간초과 : pow)

# 시간초과(pow)

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

ans = pow(a, b)

print(ans % c)

 

역시 실버는 실버인 이유가 있다.

이렇게 간단하게 풀릴 문제가 아니다.

---

문제 풀이(RecursionError : 재귀함수)

# 재귀함수(RecursionError)

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

def power(x, y):

    if y == 1:

        return x

    return x * power(x, y-1)

print(power(a, b) % c)

 

시간초과를 해결하기 위해 재귀함수도 사용해봤지만 이것 역시 RecursionError가 발생했다.

RecursionError가 발생하는 이유는 재귀 호출이 너무 깊어져서 Python의 기본 재귀 제한을 초과했기 때문이다.

Python의 기본 재귀 제한은 약 1000번이므로 b의 값이 1000이상이라면 에러가 발생한다.

---

문제 풀이(정답 : 분할정복)

# 분할정복(정답)

# Time: 460 ms

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

def divide(base, power, div):

    if power == 1:

        return base % div

    elif power % 2 == 0:

        temp = divide(base, power // 2, div)

        return (temp * temp) % div

    else:

        temp = divide(base, power // 2, div)

        return (temp * divide(base, power // 2 + 1, div) % div)

print(divide(a, b, c))

 

시간초과를 해결할 수 있는 방법 중 분할정복 이라는 개념을 알게되었다.

 

분할정복이란?

분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

 

이 문제에서는

${2^8} = {2^4} * 2^{4}$ 으로 분할하여 식을 표현할 수 있다.

 

그래서 나는 제곱이 1일 때, 짝수일 때, 홀수일 때의 경우를 나누어 코드를 작성했다.

1. power가 1일 때
   간단한 경우이다. 그냥 base값을 div로 나눈 나머지 값을 리턴하면 끝이다.
2. power가 짝수일 때
   ${2^8} = {2^4} * 2^{4}$ : 이 식처럼 코드를 작성한 후 나머지 값을 구하면 된다.
3. power가 홀수일 때
   ${2^9} = {2^4} * 2^{4+1}$ : 이 식처럼 코드를 작성한 후 나머지 값을 구하면 된다.

이렇게 코드를 작성하니 정답을 구할 수 있었다.

하지만 이 코드보다 더 빠르게 구현할 수 있는 방법도 있었다!

---

문제 풀이(정답 : 분할정복 - 최적화)

# 분할정복(최적화)

# Time: 36 ms

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

def divide(base, power, div):

    if power == 1:

        return base % div

    elif power % 2 == 0:

        temp = divide(base, power // 2, div)

        return (temp * temp) % div

    else:

        temp = divide(base, power // 2, div)

        return (temp * temp * base) % div

print(divide(a, b, c))

 

power가 홀수일 때의 코드를 재귀함수가 아닌 base를 한 번 곱해주는 것으로 수정했더니 훨씬 빠르게 코드가 실행되었다.

 

시간비교를 해보자면 처음 내가 풀었던 코드는 460ms였고 최적화 코드로 푼 속도는 36ms이다.