[1629] 곱셈 - Python

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

분할 정복 문제다.

어떤 수의 거듭제곱을 단순히 모두 곱해서 구한다면 시간 복잡도는 O(n)이지만 분할 정복을 이용해 구하면 O(log n)으로 해결할 수 있다.

 

a의 b제곱은

• b가 짝수일 경우 a^b = a^(b/2) * a^(b/2)
• b가 홀수일 경우 a^b = a^((b-1)/2) * a^((b-1)/2) * a

로 나타낼 수 있다. 따라서 재귀를 이용해 b가 1이 될 때까지 문제를 쪼개서 풀도록 구현했다.

 

또한 이 문제는 단순히 거듭제곱을 구하는 것이 아니라 나머지를 구하는 문제다. 

• a = cx + y (a를 c로 나눈 나머지는 y)

라고 한다면

• a^2 = (cx)^2 + 2cxy + y^2 = Qc + y^2

이므로, 나머지만 거듭제곱하여 모듈러 연산을 적용해도 a 전체를 거듭제곱하여 계산하는 것과 같은 결과가 나올 것이다. 따라서 a를 계속해서 거듭제곱하지 않고 매번 모듈러 연산을 적용해 계산의 비용을 줄였다.

# 정답 코드
a, b, c = map(int, input().split())

def sol(a, b, c):
    if b == 1:
        return a % c
    res = sol(a, b//2, c)
    if b % 2 == 0:
        return (res*res) % c
    else:
        return (res*res*a) % c

print(sol(a, b, c))

 

** 끝나고 찾아보니 모듈러 연산의 분배법칙을 미리 알고 있었다면 생각을 한 단계 더 할 필요가 없었을 것 같다 ^^

/* 나머지 분배 법칙 */
(A*B) % C = (A%C) * (B%C) % C

문제 풀이 중에 충분히 생각할 수 있는 내용이지만 시간 절약을 위해 기억해 놓는게 좋겠다.