[소프티어] 바이러스 - python (레벨 2)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=407 

Softeer

문제

바이러스가 숙주의 몸속에서 1초당 P배씩 증가한다. 처음에 바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 바이러스로 불어날까? N초 동안 죽는 바이러스는 없다고 가정한다.

 

입력형식

첫 번째 줄에 처음 바이러스의 수 K, 증가율 P, 총 시간 N(초)이 주어진다.
입력은 다음 조건을 만족한다.
   1 ≤ K ≤ 10^8 인 정수
   1 ≤ P ≤ 10^8 인 정수
   1 ≤ N ≤ 10^6 인 정수

 

출력형식

최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하라.

 

풀이

문제를 보았을때 알수있는 힌트

문제만 보면 단순하게 생각할수있다. k*(p^n)이 답이기 때문이다. 하지만 입력값의 최대인 10의 8승은 엄청나게 많아서 계산하기에는 많은 시간이 걸린다. 이를 분할 정복을 이용하여 O(nlogn)으로 줄일 수 있다.

import sys

input= sys.stdin.readline

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

def recursive_power(c,n):
    if n==1:
        return c
    else:
        y= recursive_power(c,n//2)%1000000007
    if n%2 ==0:
        return (y*y)%1000000007
    else:
        return (y*y*c)%1000000007
a= recursive_power(p,n)
print((k%1000000007)*(a)%1000000007)

https://github.com/dydwkd486/coding_test/blob/main/softeer/바이러스.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리