백준 1629 - 곱셈

처음 든 생각

- 일단 A, B, C 범위가 심상치가 않네 이건 뭔가가 숨겨져 있다.

 

그래서 구글링을 좀 해서 풀었다.

 

나의 답

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

def p(n):
    if n==1:
        return A % C
    else:
        tmp = p(n//2)
        if n%2 == 0:
            return tmp*tmp % C
        else:
            return tmp* tmp * A % C

print(p(B))

 

먼저 코드 설명에 분할 정복을 이용한 거듭제곱 알고리즘 부터 살펴보자.

 

https://hbj0209.tistory.com/43

[Algorithm] 분할정복을 이용한 거듭제곱

 

지수법칙을 활용해서 지수를 계속해서 2로 나눈 후 곱해가는 방식으로 N번 곱하는 것이 아니라 logN번 만큼 곱해나가는 알고리즘임을 알 수 있다.

 

이걸 코드로 가져와서 좀 더 자세히 살펴보자.

 

먼저 나머지 연산에 대해서 살펴보면 (a * b) % n = (a의 나머지) * (b의 나머지) % n 이다.

 

power 함수는 n (차수)를 매개변수로 사용한다.

만약 1차일 경우 그 때의 나머지 값을 리턴한다.

 

그게 아니라면 차수를 반으로 나눠서 다시 연산을 수행한다.

 



해당 재귀함수의 동작 과정을 손으로 써본 것이다.

 

즉 12 -> 6 -> 3 -> 1의 나머지 연산만 수행하여 전체의 나머지 계산을 할 수 있기에 시간 복잡도가 O(logN) 이다. 

문제에서 O(N)만 되도 20억번이 넘는 연산을 수행해야하기 때문에 시간 초과가 날 수 밖에 없다.

---

새로운 거듭제곱을 분할해서 계산하는 알고리즘은 처음 배웠다. 그래도 논리 자체가 어려운 편은 아니라서 이해는 금방 되었다. 다만 손으로 써보는 건 또 다른 얘기니 복습을 통한 반복이 필요할 것 같다.