[python] 백준 1629 :: 곱셈 (분할 정복, 모듈러 연산, 메모이제이션)

[곱셉]

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

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

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

풀이

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


def power(n):
    if n == 0:
        return 1  # n이 0이면 1을 반환한다.
    if n % 2 == 0:
        return (power(n//2) ** 2) % c  # n이 짝수면 power(n//2)의 제곱을 반환한다.
    # n이 홀수면 power(n//2)의 제곱에 a를 곱한 값을 반환한다.
    return ((power(n//2) ** 2) * a) % c


print(power(b))

1. 모듈러 연산

(power(n//2) ** 2) % c

1) 모듈러 연산을 해야 하는 이유

• 이 문제에서 A, B, C는 모두 2,147,483,647 이하의 자연수로 주어지는데,
  만약 A와 B가 둘 다 2,147,483,647로 주어지면 결과는 1.215 × 10^3113863045 정도의 값이 된다.
  But, 파이썬에서 표현 가능한 최대 정수값은 9.22337 × 10^18 (2^63 - 1)이다.

1.215 × 10^3113863045 >> 훨씬 크다 >> 9.22337 × 10^18

• 즉, 정수형으로 계산할 수 없는 값이다.

• 그래서 위 재귀함수에서 매 return마다 %c를 추가해서 모듈러 연산을 했다.

• %c 연산을 하면 중간 결과가 항상 c보다 작아지기 때문에 수가 어마어마하게 커지지 않는다.
  (예를 들어, c가 100이라면, 중간 결과가 항상 0~99 사이의 숫자가 된다.)

2) 모듈러 연산을 사용해도 결과가 같은 이유

(a + b) % m = ((a % m) + (b % m)) % m
(a - b) % m = ((a % m) - (b % m)) % m
(a * b) % m = ((a % m) * (b % m)) % m

• 모듈러 연산은 위와 같은 성질을 가진다.
  (나머지를 곱하든, 곱해서 나누든 똑같음!)

• 따라서, 코드에서 모듈러 연산을 마지막에 한 번만 수행하거나, 각각의 곱셈 연산마다 수행해도 결과는 동일하다.

2. 재귀함수의 메모이제이션

• 재귀 함수는 입력값이 동일하면 당연하게도 항상 같은 출력값을 반환한다!

• 같은 입력값에 대해서는 항상 같은 출력값을 반환하기 때문에, 이 값들을 저장해두면 중복 계산을 피할 수 있다.

# 이렇게 함수의 결과를 `**2`로 제곱하는 방식으로 작성하면 괜찮은데,
return (power(n//2) ** 2) % c

# 제곱하는 부분을 풀어서 아래처럼 작성하면 시간 초과가 발생한다. 🔥⏰🔥
return (power(n//2) * power(n//2)) % c

👉🏻 `power(n//2)`을 두 번씩 호출하게 되기 때문!

여기에 메모이제이션을 적용해서 시간을 줄여보자!!!

• 메모이제이션은 코드로 캐시를 만들어 이전에 계산한 값을 저장하고 재활용하는 방식이다.

명시적 메모이제이션을 활용한 코드 👉🏻 ⏰시간 초과 안 남!

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

def power(n):
    if n == 0:
        return 1
    if n in cache:  # 이전에 계산한 값이 캐시에 있는 경우, 캐시 값을 반환한다.
        return cache[n]
    if n % 2 == 0:
        result = (power(n//2) * power(n//2)) % c
    else:
        result = (power(n//2) * power(n//2) * a) % c
    cache[n] = result  # 캐시에 결과 값을 저장한다.
    return result

print(power(b))