[BOJ] 백준 1629번 곱셈 (Python)

문제

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

입력

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

출력

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

예제

입력

10 11 12

출력

풀이

def dac(a, b):
    # b가 1인 경우에는 곱할 필요가 없기에 그냥 나머지 리턴.
    if b == 1:
        return a % C

    # dac함수를 통해 a를 (b // 2)번 곱한 나머지를 구함.
    tmp = dac(a, b // 2)
    
    # b가 짝수인 경우
    if b % 2 == 0:
    	# tmp를 제곱 후 C로 나눈 나머지를 리턴.
        return tmp * tmp % C
    # b가 홀수인 경우
    else:
    	# tmp 제곱 후 a를 한번 더 곱한 후 C를 나눠야 a를 b번 곱한 후 C로 나눈 나머지가 구해짐.
        return tmp * tmp * a % C
        
        
A, B, C = map(int, input().split())

print(dac(A, B))

divide and conquer를 이용한 문제이다. 재귀함수를 이용해 경우를 나눠 다시 함수를 실행시키고, 받은 값을 합쳐 다시 리턴하는 방법.