백준 1629 곱셈 (파이썬)

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

 

 

제출 코드 (정답)

def sol(A, B, C):
    if B == 0:
        return 1

    if B%2 == 1:
        return A*sol(A, B-1, C)

    else:
        half = sol(A, B//2, C) % C
        return half * half

A, B, C = map(int, input().split())

print(sol(A, B, C) % C)

#print(pow(A,B,C))

 

결과 및 정리

 

수식은 A^B%C 인데 A, B, C 모두 21억 이하의 수라서 단순히 제곱을 하면 안되었습니다.

또한 문제가 간결한 것에 비해 정답률이 매우 낮은 것을 보고 쉬운 문제가 아니라고 생각해서 알고리즘을 통해 힌트를 얻었습니다.

 

그런데 분할 정복을 이용하여 곱셈을 해결할 수 있다는 것을 보고 납득이 가지 않아 백준의 검색을 통해 힌트를 얻었습니다.

  

그 결과 위 문제는 2가지 중요포인트가 있었습니다.

먼저 분할 정복을 이용해서 logN의 시간복잡도로 곱셈을 해결해야 합니다. 단 지수가 홀수 일 경우는 예외 처리 해줘야합니다.

그 후 분할한 값의 제곱의 값이 매우 커질 수 있는데 이는 mod 연산을 통해 값을 줄여줍니다.

중간에 mod 연산을 해도 mod 연산의 분배 법칙 때문에 값은 변하지 않습니다.

 

나머지 연산의 분배법칙
(A^B) % C = ( (A%C) ^ (B%C) ) % C 

예 (19^8) % 13 = { (19 % 13) ^ (8 % 13) } % 13 = (6^8) % 13 =  1679616%13 = 3