분할 정복 : 곱셈(백준 1629번)

▶ 문제 : https://www.acmicpc.net/problem/1629

1629번: 곱셈

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

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

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

 

▶ 접근 방법

 

▶ 풀이 코드

import sys

A, B, C = map(int, sys.stdin.readline().split())

def cal(A, B):
    if B == 1 :
        return A % C
    else :
        temp = cal(A, B // 2)

				# 짝수 / 홀수 구분해서 계산
        if B % 2 == 0 :
            return temp * temp % C
        else :
            return temp * temp * A % C

print(cal(A,B))

 

▶ 관련 링크

2021.11.17 - [알고리즘] - 분할 정복(Divide and Conquer)이란?

2021.11.17 - [알고리즘] - 분할 정복 : 색종이 만들기(백준 2630번)

2021.11.17 - [알고리즘] - 분할 정복 : 히스토그램에서 가장 큰 직사각형(백준 6549번)

2021.11.17 - [알고리즘] - 분할 정복 : 행렬 제곱(백준 10830번)

2021.11.17 - [알고리즘] - 분할 정복 : 가장 가까운 두점(백준 2261번)