(Python) 백준 1629

백준 1629

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	84576	23090	16946	26.366%

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

---

답안

import math
import sys

a, b, c = map(int, sys.stdin.readline().split())
result = 1
memo = [a % c]
for i in range(1, int(math.sqrt(b))+1):
    memo.append((memo[i-1] ** 2) % c)

for i in range(len(memo)-1, -1, -1):
    if b <= 0:
        break
    tmp = b - 2**i
    if tmp >= 0:
        result *= memo[i]
        result %= c
        b = tmp

print(result)

이 답안은 Python3가 아닌 PyPy3으로 제출해야 정답 처리됩니다.

풀이

(왜 제곱 결과에 모두 % C를 이용해 나머지 값을 받는지 모른다면, 나머지 분배 법칙에 대해 찾아보자.)

우선, 내 답안 코드는 pypy3가 아닌 python3로 제출하면 시간 초과로 오답 처리된다.

따라서 이것보다 더 나은 코드가 있을 것이라고 생각한다.

python3으로 이 문제를 맞힌 다른 사람들의 코드를 살펴보니

# kimgiho850416 님의 코드
# https://www.acmicpc.net/source/53464285

print(pow(*map(int,input().split())))

이 한 줄로 정답 처리를 받아냈는데, 내가 생각했던 것보다 pow 함수가 많이 강력했었던 것 같다..

그 외에는

# dlwnsgur0803 님의 코드
# https://www.acmicpc.net/source/54983418

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

def divide(b):
    if b == 1:
        return A % C

    elif b % 2:
        return (divide(b//2)**2 * A) % C
    
    else:
        return (divide(b//2)**2) % C

print(divide(B))

이와 같이 재귀를 이용한 분들이 많았다.

이 문제에서 주어진 시간이 0.5초밖에 되지 않는다는 점에서, 나도 $O(log(n))$의 시간복잡도로 문제를 풀어야겠다는 생각을 가지고 있었지만, 재귀가 아닌 다른 방법을 사용하였다.

memo = [a % c]
for i in range(1, int(math.sqrt(b))+1):
    memo.append((memo[i-1] ** 2) % c)

내 코드의 아이디어는 memo라는 곳에 $a^1$, $a^2$, $a^4$, $a^8$, $a^{16}$, … 을 저장하여, $a^b$를 더욱 빠르게 구하는 것이다.

예를 들어 $b=30$이라고 하면, $a^{30} = a^{16} * a^8 * a^4 * a^2$임을 이용해 네 번의 곱셈만으로 $a^{30}$을 구하는 것이다.

for i in range(len(memo)-1, -1, -1):
    if b <= 0:
        break
    tmp = b - 2**i
    if tmp >= 0:
        result *= memo[i]
        result %= c
        b = tmp

memo 리스트를 거꾸로 순회하면서, 예를 들어 $b=30$이라고 하면 $a^{16}$, $a^8$, $a^4$, … 를 계속 곱해간다.

여기서 b와 i 사이에는 지수/로그 관계가 성립하므로, b와 i를 비교할 때는 b - 2**i와 같이 주의하여 비교한다.

내 풀이와 재귀 풀이는 똑같이 $O(log(n))$ 시간 복잡도를 가지지만, 재귀 방식에 비해 내 풀이의 경우 더 많은 계산을 해야 한다는 점이 python3에서 시간 초과 오답이라는 결과를 가져다 줬던 것 같다.