[Backjoon 1629] 곱셈

문제

---

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 A, B, C는 모두 2,147,483,647 이하의 자연수이다.

시간 제한 : 0.5초

 

 

풀이

---

일단 시간 제한이 0.5초이고 입력으로 받는 수가 21억이므로 최대 O(N)으로 21억번을 곱하면 시간 초과가 날 것이다.

 

여기서 잠깐 대략적으로 왜 시간 초과가 나는지 짚고 넘어가자.

 

"수행 시간 짐작을 위한 주먹구구 법칙"이라는 것이 있는데 <입력의 크기를 시간 복잡도에 대입해서 얻은 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억을 넘어가면 시간 제한을 초과할 가능성이 존재한다. >이다!

 

자 그럼 만약 O(N)으로 알고리즘을 짜면 21억 -> 21억초이므로 시간 안에 돌아갈 가능성이 없다.

 

그러므로 이 문제는 "분할 정복" 알고리즘으로 접근해야한다.

 

만약 2^5을 계산하면 2 * 2 * 2 * 2 * 2로 총 5번의 연산을 수행하지만, 분할 정복을 사용하면 2^2 * 2^2 * 1로 O(logN)으로 줄어든다.

 

log(2,147,483,647) = 31로 분할 정복을 사용하면 충분히 해결할 수 있다.

 

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

# 0.5s
def solution(a, b, c):
    if b == 0:
        return 1
    x = solution(a, b//2, c)
    
    if b % 2 == 0:
        return x * x % c
    else:
        return x * x * a % c 

print(solution(a, b, c))

 

2^5 분할 정복 예시

 

 처음에 모든 연산을 수행하고 c로 나누어서 시간 초과가 났다.