# 문제
자연수 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))
(power(n//2) ** 2) % c
1.215 × 10^3113863045
정도의 값이 된다.9.22337 × 10^18 (2^63 - 1)
이다.1.215 × 10^3113863045 >> 훨씬 크다 >> 9.22337 × 10^18
즉, 정수형으로 계산할 수 없는 값이다.
그래서 위 재귀함수에서 매 return마다 %c
를 추가해서 모듈러 연산을 했다.
%c
연산을 하면 중간 결과가 항상 c보다 작아지기 때문에 수가 어마어마하게 커지지 않는다.
(예를 들어, c가 100이라면, 중간 결과가 항상 0~99 사이의 숫자가 된다.)
(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`로 제곱하는 방식으로 작성하면 괜찮은데,
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))