[Python] 백준 1629번(곱셈) 문제 풀이

 

이 문제를 보고 나는 정말 쉽다 생각해 신나서 코드를 짰다.

 

abc = list(map(int, input().split()))
print((abc[0]**abc[1])%abc[2])

 

 하지만 그러고 제출해 보니...

 

 

 ...? 시간 초과...?

 

 알아보았더니 이 문제는 Divide and Conquer(DAC), 즉 분할 정복의 원리를 사용해야 풀리는 문제였다.

 

 예를 들어, 2^32라면 2를 32번 곱하는 방법도 있지만, (2^16)^2로 해서 풀면 2를 16번 곱한 것을 다시 2번 곱하니 17번의 연산만으로 끝낼 수 있어 시간이 훨씬 적게 든다. 이를 계속 해보면 {(2^8)^2}^2 이렇게 풀면 10번만에, [{(2^4)^2}^2]^2 이렇게 풀면 7번만에 끝낼 수 있어 시간이 획기적으로 주는 것이다.

 

def dac(a, b, c):
    if b == 1:
        return a % c
    elif b % 2 == 0:
        return (dac(a,b//2,c)**2)%c
    else:
        return ((dac(a,b//2,c)**2)*a)%c

abc = list(map(int, input().split()))
print(dac(abc[0], abc[1], abc[2]))

 

 그래서 이 블로그를 참고하여 코드를 한번 짜 보았다.

 

 a, b, c를 입력받는 함수 dac를 만든다. 만약 b가 1이라면 (a**1)%c를 출력하는데, 어떤 수의 1승은 그 수 자신이기 때문에 b가 1이면 a%c를 return한다. 만약 b가 짝수라면, dac 함수에 다시 넣는데, a의 b//2승을 한 뒤 다시 2를 곱해주는 것이다. 만약 b가 홀수라면 a의 b//2승을 계산한 뒤 2를 곱하고 다시 a를 곱하여 a의 b승을 만들어 준다.

 

 

 생각보다 어려웠던 문제였다.