[Softeer/Python] H-클린알파 ★★★★☆ - 효과는 굉장했다

 

Softeer

 

 

SOLUTION

import sys

P, N = map(int, sys.stdin.readline().split())
virus = list(map(int, sys.stdin.readline().split()))

ans = 0 
mod = 1e7

for i in range(N-2, -1, -1):
    # pow 함수를 이용해 효율적인 나머지 연산
    virus[i] *= pow(P, (N-i-1), mod)

print(sum(virus) % mod)

pow() 함수를 이용해 효율적인 나머지 연산을 하여 시간 복잡도를 줄여서 통과 시킬 수 있다.

만약, 나머지를 pow(P, (N-i-1), mod) 형태가 아닌 pow(P, (N-i-1) % mod 형태로 해주게 된다면 

시간초과가 뜨게 된다.

 

그 이유는 pow함수 안에 나머지를 선언하면 고속 거듭제곱의 형태로 곱해주는 O(logN)의 시간 복잡도를 가지기 때문에

그냥 나누어 주는 O(N)의 시간복잡도 보다 효율적인 계산을 할 수 있게 된다.