문제
바이러스가 숙주의 몸속에서 1초당 P배씩 증가한다. 처음에 바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 바이러스로 불어날까? N초 동안 죽는 바이러스는 없다고 가정한다.
입력
첫 번째 줄에 처음 바이러스의 수 K, 증가율 P, 총 시간 N(초)이 주어진다.
입력은 다음 조건을 만족한다.
인 정수
인 정수
인 정수
출력
최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하라.
예시
입력
2 3 2
Plain Text
복사
출력
18
Plain Text
복사
정답
import sys
K, P, N = map(int,sys.stdin.readline().split())
print(K*pow(P,N, 1000000007)%1000000007) # pow(P, N, S) = P를 N 거듭제곱한 것을 S로 나눈 값 -> pow(P,N)%S 보다 훨씬 효율적
Python
복사
풀이
•
pow의 기능을 잘 알고있는지 물어보는 문제이다.
•
단순히 문제를 따라가서 다음과 같이 풀면 시간초과가 나온다.
import sys
K, P, N = map(int,sys.stdin.readline().split())
print(K*pow(P,N)%1000000007)
Python
복사
•
따라서 pow(P,N,S)를 사용해야 한다.
•
pow(P,N,S)는 P를 N제곱한 것을 S로 나눈 값을 출력해준다. 이는 pow(P,N)%S 보다 훨씬 효율적으로 처리를 하기 때문에 시간도 훨씬 적게 걸리는 장점이 있다.
•
따라서 pow(P,N,1000000007)로 나머지를 구하고 여기에 K를 곱해서 다시 1000000007로 나눠주면 된다. → K를 곱했을 때 1000000007보다 커질 수 있기 때문.
•
X*Y를 Z로 나눈 나머지는 Y를 Z로 나눈 나머지에 X를 곱하고 Z로 다시 나눈 나머지와 같다.
print(K*pow(P,N, 1000000007)%1000000007) # pow(P, N, S) = P를 N 거듭제곱한 것을 S로 나눈 값 -> pow(P,N)%S 보다 훨씬 효율적
Python
복사