[DevLog][Baekjoon] 1629: 곱셈

[1629] 곱셈

1) 문제

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

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입/출력

10 11 12
# output is 4

2) 풀이

$\ A^(x+y) = A^x \times A^y$ 임을 이용해 분할 정복으로 풀어야겠다는 생각은 들었는데, 구체적인 구현방법이 떠오르지 않았다. 결국 풀이를 참고했고, 핵심은 모듈러 연산의 성질이라는 점을 알게 되었다.

모듈러 연산의 분배법칙

$(A \pm B), \bmod, C = [(A,\bmod,C)\pm(B,\bmod,C),\bmod C] $
$(A \times B), \bmod, C = [(A,\bmod,C)\times(B,\bmod,C),\bmod C] $

접근법

A의 지수인 B를 2로 나누어가면서 mod C 를 수행하고, 짝수/홀수 여부에 따라 연산된 값을 모두 곱하여 다시 mod C 하는 과정을 재귀적으로 수행한다.

# pseudo code
# A^B % C 를 연산하라

modulo(A, N):
  IF N == 1:
    return A % C

  K = modulo(A, N//2)
  IF N is odd:
    return A * K * K % C
  ELSE:
    return K * K % C

# example
A = 3, B = 6, C = 2 이면

modulo(3, 6)
    modulo(3, 3)
        modulo(1, 3)
        리턴 3 % 2 = 1
    3이 홀수이므로
    리턴 3 * 1 * 1 % 2 = 1 # (A * (A mod C) * (A mod C)) mod C
6이 짝수이므로
리턴 1 * 1 % 2 = 1

처음에는 B를 두 수의 합으로 나누어 각각 재귀함수를 호출하는 코드로 생각했는데, 한 번만 호출해 tmp 변수에 넣어 두고 짝/홀 여부에 따라 값을 리턴해줘도 충분하다는 것을 알게 되었다. 오랜 시간 고민했지만 결국 풀지 못해 아쉬움이 남는다🥲 풀이를 보고 이해하는 과정이 다음 스텝에서 또 도움이 되겠지, 하는 바램

03) 코드 (파이썬)

import sys
sys.setrecursionlimit(10**8)

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


def modulo(n):
    if n == 1:
        return (A % C)

    tmp = modulo(n//2)
    if n % 2 == 0:
        return tmp * tmp % C
    return A * tmp * tmp % C


print(modulo(B))