[Baekjoon 1629 / python / 실버1] 곱셈

def dac(a, b, c): # a^b % c

    if b == 1:

        return a % c

    elif b % 2 == 0: # b가 짝수일 때

        return (dac(a, b//2, c)**2) % c

    else:

        return ((dac(a, b//2, c)**2)*a) % c

a, b, c = map(int, input().split())

print(dac(a, b, c))

 

분할 정복 알고리즘이 사용되며, (a ^ b) % c 의 결과를 출력하기만 하면 되는 문제이다.

 

그러나 주어지는 입력값이 int의 최대값인 21억 정도로 매우매우 크다.

시간 제한도 0.5초로 매우 짧기 때문에 일반적인 연산으로는 시간 초과가 뜬다.

때문에 수학 공식을 이용하여 작은 단위로 분할하여 연산 횟수를 줄여서 계산해야 한다.

 

2^32 == (2^16)^2  두 값은 동일하지만, 파이썬의 연산횟수는 32번과 17번으로 매우 차이가 크다. 마찬가지로 {(2^8)^2}^2도 동일하고 더 분할해도 동일하다. 이렇게 2^1이 될 때까지 분할하는 것이다.

 

또한, "(a * a) % c" 는 "(a % c) * (a % c) % c" 와 동일하다. 나머지를 구하는 연산에 대해선 a 를 a%c로 치환할 수 있다.

"return (dac(a, b//2, c)**2) % c" 부분은,

"return (a % c) * (a % c) % c" 를 표현한 것이다. 

b가 홀수일 경우는 a를 한번 더 곱해줘야 하기 때문에 *a 연산을 추가하였다.

 

이런 방식으로 (a ^ b)%c 를 (a ^ b//2)%c 로 분할하는 것을 재귀적으로 구현했다. 나는 수학을 전혀 못 해서 이해가 매우 어려워 옆에서 함께 공부하는 팀원에게 질문해 겨우 이해할 수 있었다.

이 문제는 분할 정복 알고리즘을 연습하기 위한, "문제를 위한 문제"인 것 같다.