Softeer 슈퍼바이러스 (난이도3)

정답 코드

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

def cal(n, p):
    if n == 1:
        return p
    ans = cal(n // 2, p)
    if n % 2:
        return ans * ans * p % 1000000007
    else:
        return ans * ans % 1000000007


print(K * cal(N * 10, P) % 1000000007)

알고리즘 유형

divide and conquer

배운 점

시간 초과 문제 때문에 애를 많이 먹었다.
logN으로 만들 수 있는 것을 linear하게 풀다보니 시간이 말도 안 되게 길어졌기 때문이다.
알고리즘 문제풀이에서 언제나 가장 중요한 것은 log로 만드는 것. 명심 또 명심.