[백준] 1629번: 곱셈 - 파이썬

📕 풀이 

A와 B와 C가 공백을 두고 입력된다. 우리는 (A^B)%C 값을 출력하면 된다. 단 A,B,C 는 모두 2,147,483,647 이하의 자연수이다.

수의 범위가 방대하다. 때문에 21억번 곱한다면 O(N)이여도 시간초과가 날 것이다. 
그래서 나머지 분배법칙과 지수법칙을 사용하여 답을 구하였다.

 

📖 지수법칙

(A^m)^n = (A^(m * n))

 

📖 나머지 분배 법칙

(AxB) % C = (A%C) * (B%C) % C

 

우선 지수 법칙을 사용하여 분할 정복을 한다. 2 ^ 32 의 값을 계산하는 방법은 2를 32번 곱하는 방법도 있지만 지수법칙을 사용하여 (2^16)^2 16번 곱한 것을 제곱하는 방식으로 하면 총 17번의 연산으로 줄일 수 있다. 이 방법을 계속 사용하면 10번, 연산 7번만에 결과에 도달할 수 있다. 

 

만약 B가 1이라면 A 1제곱이라는 의미이기에 바로 그냥 A%C를 리턴해준다.

 

예제를 가지고 설명해보자

 

A : 10, B : 11, C : 12

 

예제는 우선 B가 홀수이다. 

 

((A^5)*(A^5)*A)%C 를 수행해줘야 한다.

한번 더 진행하면,,

(((A^2)*(A^2)*A)*((A^2)*(A^2)*A)*A)%C 이렇게 된다!

 

문자를 다시 숫자로 바꿔보자면,,

 

(10^5)(10^5)*10 이 경우는 B가 홀수일 경우이다. 제곱꼴에 A를 한번 더 곱해준다.

 

B 가 짝수라면 A를 한번 더 곱해주지 않아도 된다.

 

 

💻 코드

def solve(a,b,c):
    if b == 1: # 거듭제곱을 할 필요없음 바로 a의 나머지 리턴
        return a%c
    else:
        k = solve(a, b//2, c)
        if b%2 == 0: # b가 짝수라면 
            return (k*k)%c
        else: # b가 홀수라면
            return (k*k*a)%c
a,b,c = map(int, input().split())
print(solve(a,b,c))

 

📎 문제 링크 : 곱셈

1629번: 곱셈

 

도움받은 글들 : 개발 탄약고 , grace0st