[백준알고리즘/1629번/파이썬] 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

문제: 숫자 A,B,C 가 주어졌을 때, A를 B번 곱했을 때 C로 나눈 나머지를 구하는 문제입니다.

 

풀이 방법: 분할 정복 방식으로 풀었습니다.

 

풀이 코드:

import sys

a,b,c = map(int,sys.stdin.readline().split())

def DivideAndConquer(num1,num2):
    if num2 == 1:
        return num1 % c

    tmp = DivideAndConquer(num1,num2//2)
    if num2 % 2 == 0:
        return tmp ** 2 % c
    else:
        return tmp**2 * num1 % c
print(DivideAndConquer(a,b))

풀이 설명:

나누는 수인 b가 짝수일 경우와 홀수일 경우를 나누어 생각했습니다.

입력 예제인 10,11,12로 예시를 들어보겠습니다.

 

b가 짝수 일 경우(a= 10, b = 10 ,c =12), 10^5 * 10^5로 나눌 수 있습니다.

b가 홀수 일 경우에는 (a=10, b=11, c=12), 10^5 * 10^5 * 10으로 나눌 수 있죠.

 

위와 같은 분할에다가, 나머지연산에 다음과 같이 분배 법칙을 적용할 수 있습니다.

(a*b)%c = ((a%c) * (b%c)) % c 로 분배법칙이 성립하죠.

 

분할과 분배법칙을 적용하여, 문제가 풀리도록 코드를 구성해주었습니다.