백준 1629번 곱셈 [Python]

input 값이 A,B,C 모두 2,147,483,647 이하의 자연수라고 명시되어 있다. 그렇기 때문에 반복문을 이용하여 문제를 풀게되면, 시간 초과가 나올 것이다. 

 

시간 초과가 나왔던 풀이

1. 반복문

2. print((A**B) % C)

 

문제를 해결하기 위해 python method를 찾다가 pow라는 method를 발견했다.

pow(x, y[, z])

 

분할 정복 방식

 

지수가 짝수일 경우 A^B * A^B 로 나눌 수 있고,

지수가 홀수일 경우 A^B * A^B * A로 나눌 수 있다.

 

B를 2에 대한 거듭제곱 형태로 계속하여 분할하여 B만큼 A를 거듭제곱 하는 것이 아니라 제곱을 한 뒤, 거기에 제곱을 또하고 또하는 방식을 취하여 연산 수를 최대한 줄여가는 방식이다.

 

 

 

참조:

https://tmdrl5779.tistory.com/114

https://www.programiz.com/python-programming/methods/built-in/pow