[Baekjoon] 1629. 곱셈

문제 설명

문제

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

입력

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

출력

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

예제 입력 1

10 11 12

예제 출력 1

4

문제 풀이

# 분할정복

어떤 수의 거듭 제곱을 분할 정복을 이용해 빠르게 구할 수 있습니다.

분할 정복과 메모이제이션을 함께 사용합니다.

def cal_power(n,k,c): # n^k
    if k in memo: pow = memo[k]
    elif k % 2 == 0: pow = cal_power(n,k//2,c) * cal_power(n,k//2,c)
    else: pow = cal_power(n,1,c) * cal_power(n,k-1,c)
    
    if k not in memo: memo[k] = pow % c
    return memo[k] % c

A, B, C = map(int,input().split())
memo = {0:1,1:A}
print(cal_power(A,B,C))

memo라는 딕셔너리에 memo[k] = n의 형태로 메모이제이션을 정의합니다.

7번 라인에서 memo[k] % c를 해준 것은 1 1 1과 같은 입력 케이스 때문입니다.