백준 1629번 "곱셈"

문제

백준 1629번 곱셈

풀이

문제를 있는 그대로 접근해서 (a^b)%c를 계산하면 시간초과가 뜬다.

시간을 줄이기 위해선 분할 정복을 이용하여 문제를 해결해야 한다.

b가 홀수일 경우,
(a^(b//2))^2 * a
b가 짝수일 경우
(a^(b//2))^2 와 같이 나누어 주어 계산해야 한다.
재귀를 이용하여 b가 1이 될 때 까지 나누어 계산하면 O(n)의 시간복잡도가 O(log2n)의 시간 복잡도로 대폭 낮아진다.

또한 입력으로 주어지는 a, b, c의 최대값이 크므로 각 계산마다 %c를 해주어야 한다.

Python 코드

import sys
input = sys.stdin.readline

def solve(power):
  if power == 1:
    return a%c

  if power%2 == 0:
    return solve(power//2)**2 % c
  else:
    return solve(power//2)**2 * a % c

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

print(solve(b))