곱셈 [백준 1629] - python

import sys 
input = sys.stdin.readline 

def BOJ1629() :
  def pow(a, b, c) :
    if b == 1 :
      return a % c
    elif b % 2 == 0 :
      return (pow(a, b // 2, c) ** 2) % c
    else :
      return (pow(a, b // 2, c) ** 2) * a % c
  
  A, B, C = map(int, input().split())
  print(pow(A, B, C))
  
BOJ1629()

접근 방법: 

1. 쉽게 보았는데 크게 데였다. A, B, C의 범위가 매우 크고 시간 제한은 0.5초, 메모리 제한도 128MB여서 A의 B제곱을 구한 후 모듈러 연산을 통해 답을 구할순 없었다.

2. a^4 = a^2 ** 2
    a^5 = a^2 ** 2 * a 를 이용한 분할제곱을 이용하여 거듭제곱의 값을 알아내고자 했다.

3. 재귀함수는 코드의 흐름을 이해하기가 어려워 선호하지 않지만 이번 문제는 거듭제곱으로 접근하였다.

pow(10, 11, 12) => (pow(10, 5, 12) ** 2) * 10 % 12
pow(10, 5, 12) => (pow(10, 2, 12) ** 2) * 10 % 12
pow(10, 2, 12) => (pow(10, 1, 12) ** 2) 

pow(10, 1, 12) => 2
pow(10, 2, 12) => 4
pow(10, 5, 12) => 4
pow(10, 11, 12) => 4

4. 재귀함수의 탈출 부분은 b가 1은 1제곱을 뜻하므로 a%c를 return 해주는 것으로 정의하였다.

    진행 부분에서는 분할제곱의 흐름을 그대로 나타내고자 하였다.

 

 

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

1629번: 곱셈