[백준 1629번] 곱셈 (Python/파이썬)

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

1629번: 곱셈

분할정복을 이용한 거듭제곱이다.

예제를 봐보자.

10의 11승을 구해야하는데 원래 같았으면 10을 11번 곱해서 구했을 것이다. 하지만 분할정복을 사용하면

4번의 계산으로 구할 수 있다.

ans = 10 * 10^2 * 10^83번처럼 보이지만 10^2에서 10^8까지 가는데 반복문이 2번돌기 때문에 4번이라고 하였다.10^11 = 10 * (10^5)^2 = 10 * (10 * (10^2)^2)^2 = 10 * (10 * (10 * 10)^2)^2위와 같이 제곱수가 짝수 일때는 (k)^2으로 묶어주고 홀수 일때는 k * (k)^2으로 묶어줌으로써 연산을 기하급수적으로 줄일 수 있다.사실 위의 과정은 제곱으로 계속 묶어나가기 때문에 2진수로 간단히 이해할 수 있다.11 = (1011) 이므로 10 * 10^2 * 10^8로 나타낼 수 있는 것이다.

코드는 다음과 같다.

import sys
input = sys.stdin.readline
A, B, C = map(int,input().split())
ans = 1
while B > 0:
  if B % 2:
    ans *= A
    ans %= C
  A *= A
  A %= C
  B //= 2
print(ans)

 

 

분할정복을 사용했음에도 한번 틀렸는데 큰 수가 곱해질수록 당연하게 숫자가 너무 커져서 간단한 연산도 상당히 오랜시간을 잡아먹는다. 따라서 계산 도중에 C로 나눠주는 과정이 필요한데, 이걸 까먹었다.

예전 문제에서도 이거 때문에 시간초과에 걸렸었는데 또 실수하다니, 정신차리고 반성한다.