[백준 1629] 곱셈 - 파이썬 풀이 (실버1)

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

---

문제 요약

a ** b % c를 리턴해야 한다.

단, 이때 위 식 그대로 출력하게 되면 시간초과가 발생한다.
분할 정복으로 풀거나, 혹은 파이썬의 pow 함수를 이용한다.
아래 두 개의 풀이 모두 정답이 된다.

---

풀이 1

# 백준 1629 곱셈 실버1 https://www.acmicpc.net/problem/1629
a, b, c = map(int, input().split())
# 2**10 = 2**5 * 2**5
def div(a, b):
    if b == 1:
        return a % c
    temp = div(a, b // 2) # 분할
    # b가 짝수일 때
    if b % 2 == 0:
        return temp * temp % c
    # a가 홀수일 때
    else:
        return temp * temp * a % c

print(div(a, b))

분할 정복 풀이법이다. $2^{10}$은 $2^5 * 2^5$ 로 표현할 수 있다. 즉, 2를 10번 곱하는 대신 $2^5$를 2번 곱하면 되는 것이다.
이러한 방식으로 분할해가면서 계산한다. 이때, 우리는 나머지를 리턴해야 하므로 b가 짝수인지 홀수인지에 따라서 return 값을 달리 해준다.

풀이 2

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

pow의 세 번째 인자를 넣으면 'a를 b번 제곱한 것을 c로 나눈 나머지를 리턴해라'라는 의미가 된다.