알고리즘 유형 : 분할 정복
풀이 참고 없이 스스로 풀었나요? : △
https://www.acmicpc.net/problem/1629
소스 코드(파이썬)
import sys
input = sys.stdin.readline
A, B, C = map(int, input().split())
def square(N, k, d):
if k == 0:
return 1
elif k == 1:
return N % d
tmp = square(N, k//2, d)
if k % 2:
return (tmp * tmp * N) % d
else:
return (tmp * tmp) % d
print(square(A, B, C))풀이 요약
-
N^k에 대해,
k가 홀수이면 N^(k//2) N^(k//2) N
k가 짝수이면 N^(k//2) * N^(k//2) 로 분할해서 계산한다
-
분할 정복이므로 재귀를 사용하는데, 홀수 짝수 조건문으로 분리해주기 전에 미리 N^(k//2)를 호출해놓고, 그 값을 활용해서 if문을 작성하면 하위 호출을 한 번만 해주면 되게 된다.
-
k가 최대 값인 2147483647이라 했을 때, 이는 2^31이고, k//2로 계속 호출되므로 재귀 깊이는 31이다.
각 재귀에서 시간복잡도는 O(1)이므로 연산 횟수도 적고, 재귀 깊이도 적으므로 TLE(시간 초과, Time Limit Exceeded) 가 발생하지 않는다.
배운 점, 어려웠던 점
-
모듈로 연산(나머지 연산)의 분배법칙을 배우고, 곱셈에 대해 나머지 연산을 분배해도 성립하는 이유를 납득하게 되었다.
-
처음에 수의 범위가 21억으로 너무 방대해서, 그냥 단순 재귀로 풀어버리면 깊이가 너무 깊어져 스택 오버플로우가 발생할 것 같아 DP 메모이제이션을 적용했더니, 도리어 길이가 21억이 넘는 리스트의 경우 때문에 메모리 초과가 떴다. 다시 생각해보니, 처음에 풀 때 홀수, 짝수 실행문에서 일일이 square(N, k//2, d)를 작성해서 여러 번 호출하게 작성했었는데, 이럴 필요 없이 조건문 이전에 tmp에 미리 구해놓고 그걸로 if문을 작성하면 되는 것이었다. 그러면 호출도 한 번만 하게 된다.
그리고 또 내가 간과했던 핵심적인 부분이 있었다. k가 최대인 2147483647 = 2^31 일 때, 재귀로 풀어도 깊이가 31밖에 되지 않는다.
