boj_1009_분산처리

문제

https://www.acmicpc.net/problem/1009

1009번: 분산처리

 

내 풀이

• 단순하게 제곱으로 접근할 시 시간초과가 난다.
  • pow(x, y[, z])If a third parameter is present, it returns x to the power of y, modulus z.
  • The `pow()` function returns the value of x to the power of y (xy).
• pow 함수나 **연산자는 내부 로직에서 같은 라이브러리 함수를 사용하기 때문에 시간 차이가 나지 않는다.
  • 하지만 pow(x,y,z) 와 a**b%c는 압도적인 속도 차이가 난다.
  • 아래는 timeit 함수를 이용하여 시간을 측정한 결과이다.

show_timeit('a ** b % 10', 'a = 30; b = 400') 
show_timeit('a ** b', 'a = 30; b = 400') 
show_timeit('pow(a, b, 10)', 'a = 30; b = 400') 
show_timeit('pow(a, b)', 'a = 30; b = 400')

a = 30; b = 400; a ** b % 10:
1.8108850999269634

a = 30; b = 400; a ** b:
1.5049420001450926

a = 30; b = 400; pow(a, b, 10):
0.5822447999380529

a = 30; b = 400; pow(a, b):
1.5555299001280218

 

타인의 풀이

• 다른 분들은 1의 자리가 반복되는 걸 이용해서 푸는 경우가 많은 것 같다.

 

참고문서

https://stackoverflow.com/questions/48839772/why-is-time-complexity-o1-for-powx-y-while-it-is-on-for-xy

https://www.w3schools.com/python/ref_func_pow.asp