백준 1629번: 곱셈

✔ 풀이를 위한 아이디어

• 분할 정복 (Divide-and-conquer) 을 이용한 거듭제곱
• 나머지 (Modulo) 연산 분배법칙
  
  

✔ 수정 전 코드 [시간 초과]

import sys

A, B, C = map(int, sys.stdin.readline().split())

def dcSquare(n):
    if n == 1:
        return A
    x = dcSquare(n//2)
    if n % 2 == 0:
        return x * x
    else:
        return x * x * A
        
print(dcSquare(B) % C)

• 어떤 수를 N번 거듭제곱 한다고 했을 때, 일반적으로 그 알고리즘은 O(N)의 시간복잡도를 갖는다.
  
• 위의 점화식과 같은 원리로 이루어지는 분할 정복 (Divide-and-conquer) 을 이용한 거듭제곱은 O(logN)의 시간복잡도로 거듭제곱의 값을 구할 수 있도록 한다.
• 이를 구현하기 위해서 재귀함수의 호출을 통해 아래와 같이 구현할 수 있다. (아래에서부터 시작한다고 생각하고 보면 된다)
  
• 그러나 이렇게 코드를 제출 했더니 시간 초과를 받게 되었다. 아마도 원인은 거듭제곱 하는 수가 너무 커지기 때문인듯 했다.
  
  

✔ 수정 후 코드

import sys

A, B, C = map(int, sys.stdin.readline().split())

def dcSquare(n):
    if n == 1:
        return A % C
    x = dcSquare(n//2)
    if n % 2 == 0:
        return (x * x) % C 
    else:
        return (x * x * (A % C)) % C
        
print(dcSquare(B))

• '나머지 연산 분배법칙'에 의하면, 곱셈으로 연결된 수의 나머지 값은 각 요소들의 나머지 값을 곱한 수의 나머지 값과 같다.
  (A x B) % p = ((A % p) x (B % p)) % p
  https://velog.io/@gidskql6671/나머지Modulo-연산-분배법칙
• 따라서 return 해주는 수에 매번 나머지 연산을 수행해 줌으로써 훨씬 더 작은 수의 곱셈으로 대신할 수 있다. 이 방식을 선택하였더니, 시간 초과를 모면할 수 있었다. (이것저것 테스트 해보느라 조금 여러번 제출했다.)