[Softeer] 바이러스

상당히 간단한 문제다.
그런데 정답률이 30프로대 여서 왜지? 하면서 풀었다..
그렇다. 틀렸다.. 정말 정말 매우 중요한 사실을 간과하고 훅 풀어버려서 그렇다.

우선 틀린 코드를 보면

import sys
input=sys.stdin.readline

k,p,n=map(int, input().split())

ans = k*(p**n)
print(ans%1000000007)

위와 같이 풀었었는데, 틀렸다가 나왔다.
여기서 주목할점은 바로 문제에서 주어진 수의 범위이다.
1<=K<=100000000(1억)
1<=P<=100000000(1억)
1<=K<=1000000(100만)

수의 범위가 너무 커서 시간초과가 나는것이다.
한번 빅오로 보면 O(1억*(1억)^(100만)) 이 되는것이다.

위의 사항을 인지하고 코드를 고쳐보면

import sys
input=sys.stdin.readline

k,p,n=map(int, input().split())

for _ in range(n):
    k=k*p
    k=k%1000000007
print(k)

위와 같이 한번의 연산이 끝나고 1000000007으로 나눈 나눗셈을 반환함으로써 수의 크기를 작게 유지해주는 것이다.

정리를 해보면 시간복잡도는 O(n)인데, 이건 for문 때문에 일어난 시간초과가 아닌, 연산하는 수가 기하급수적으로 커져서 일어나는 시간초과를 조심해야하는 문제이다.

따라서 변수의 범위를 잘 보고, 복잡도를 체크해보자.