[Softeer 연습문제] Lv2. 바이러스 (python)

[Softeer 연습문제] Lv2. 바이러스

문제확인 : https://softeer.ai/practice/6284

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

☠️ 내가 작성한 코드

import sys

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

for i in range(N):
    K *= P
print(K%1000000007)

 

- 이 코드로 제출하니 시간초과가 떴다..

- 왜그런지 찾아보니 GPT한테 물어보니까 아래의 이유 때문에 오버플로우가 발생한다고 한다.

 

• N이 최대 1,000,000 (10^6) 이므로, 거듭제곱 연산이 O(N) 시간이 걸립니다.
• 그리고 P가 최대 100,000,000 (10^8) 이면, P**N의 결과는 어마어마하게 커집니다.

 

💡 정답 코드

import sys

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

for i in range(N):
    K = (K * P) % 1000000007
    
print(K)

 

- 모듈러 연산의 성질과 반복문을 통한 점진적인 연산 때문에 오버플로우 발생 X