[백준/Python] 곱셈

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

 

---

분할 정복을 이용한 문제

A=4, B=16일 때

 

4**16

= (4^8) * (4^8)

     = (4^4) * (4^4)

          = (4^2) * (4^2)

              = (4^1) * (4^1)

 

만약 B가 홀수라면

A=4, B=17일 때

 

4**17

= (4^8) * (4^8) * 4

 

B가 홀수일 때와 짝수일 때를 나눠서 분할 정복을 해주면 된다

 

+ 나머지 계산

C를 이용해 나머지 계산을 할 때

나머지 연산 분배 법칙을 이용한다

a / n을 한 몫을 q1, 나머지를 r1

b / n을 한 몫을 q2, 나머지를 r2 라고 했을 때

 

a = (q1 * n) + r1

b = (q2 * n) + r2

 

(a × b)

= ( (q1 ​× n) + r1​ ) × ( (q2​ × n) + r2 ​)

= ( (q1​ × n × q2 ​× n) + (q1 ​× n × r2​) + (q2 ​× n × r1​) + (r1 ​× r2​) )

 

(a × b) % n

= ( n^2(q1 × q2) + n(q1 × r2) + n(q2 × r1) + (r1 × r2)) % n

일 때 n의 배수는 %n을 했을 때 나머지가 0이다

 

그래서 남는 식은

= (r1 * r2) % n

 

그런데 r1은 a%n이고 r2는 b%n이므로

= (a%n × b%n) %n

이 된다.

 

 

참고:

https://velog.io/@sw801733/%EB%82%98%EB%A8%B8%EC%A7%80-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99-%EB%AA%A8%EB%93%88%EB%9F%AC-%EC%97%B0%EC%82%B0

나머지 연산 분배법칙 (모듈러 연산)

 

 

이를 토대로 코드를 작성해보겠습니다.

def dac(A, B, C):
    if B == 1:
        return A%C
    
    if B%2 == 0: # 짝수일 때
        return (dac(A, B//2, C) * dac(A, B//2, C))%C
    else: # 홀수일 때
        return (dac(A, B//2, C) * dac(A, B//2, C) * A)%C

이렇게 되면 시간초과가 납니다

그러므로 중복이 되는 dac(A, B//2, C)를 변수로 지정하겠습니다.

 

def dac(A, B, C):
    if B == 1:
        return A%C
    
    tmp = dac(A, B//2, C)
    if B%2 == 0:
        return (tmp * tmp)%C
    else:
        return (tmp * tmp * A)%C