[Softeer] [파이썬] [Level 3] 수퍼바이러스
[13일차] [코딩테스트] [Python]
🎀 본 게시물은 Softeer 연습문제 풀이 게시물입니다. 🎀
https://softeer.ai/practice/info.do?idx=1&eid=391
문제
수퍼바이러스가 숙주의 몸속에서 0.1초당 P배씩 증가한다.
처음에 수퍼바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 수퍼바이러스로 불어날까?
N초 동안 죽는 수퍼바이러스는 없다고 가정한다.
수퍼바이러스는 일반 바이러스에 비해서 훨씬 오래 생존할 수 있기 때문에 N이 매우 클 수 있다.
제약조건
\(1 ≤ K ≤ 10^8\) 인 정수
\(1 ≤ P ≤ 10^0\) 인 정수
\(1 ≤ N ≤ 10^{16}\) 인 정수
입력형식
첫 번째 줄에 처음 바이러스의 수 K, 증가율 P, 총 시간 N(초)이 주어진다.
출력형식
최종 바이러스 개수를 1000000007로 나눈 나머지를 출력한다.
입력예제1
1 2 1
출력예제1
1024
시간초가가 난다.
먼저 0.1초에 P배씩 증가하는 공식은 다음과 같다. \[iterN = N*10\] \[result = K * P^{iterN}\]
이걸 그대로 위에 바이러스문제에서 사용한 공식처럼 생각하면 시간초과가 날거라는걸 예상할 수 있다.
시간제한이 2초라서 파이썬기준 4천만정도의 연산이 가능한데.. 입력값 k, p, n 모두 4천만보다 큰 값이기도 하고,
반복문의 입력으로 사용되는 n이 특히나 1경정도라서 절대 불가능하다.
파이썬 거듭제곱 제귀함수를 검색해보자
핵심
분할정복 활용
지수법칙을 잘 활용하면 a의 n제곱을 보다 효율적으로 구할 수 있다.
두 거듭제곱 간 밑인 a가 같을 때, a의 n제곱과 a의 m제곱을 곱한 수는 두 지수 n과 m을 더한 값을 지수로 취하는 \(a^{(n+m)}\)로 표현할 수 있다.
이를 활용하면, \(a^n\)을 \(a^{(n / 2)} * a^{(n / 2)}\)로 표현할 수 있다.
수식으로 표현해 한 눈에 들어오기 힘들다면 수를 직접 넣어서 살펴보자.
\(2^4\)은 \(2^2\) 와 \(2^2\)를 곱한 것이다.
즉, \(2^4 = 2^2 * 2^2\)인 것이다.
그렇다면 n이 2로 나누어 떨어지지 않는 홀수라면 어떻게 될까? 그냥 a를 한 번만 더 곱해주면 간단히 해결된다.
즉, \(a = 2\), \(n = 5\)라고 했을 때,
\(2^5 = 2^2 * 2^2 * 2\) 로 표현할 수 있다.
이는 즉, \(2^2, 2^2, 2^1\)을 모두 곱해준 것으로, 지수를 모두 더해주면 \(2 + 2 + 1 = 5\)로, \(2^5\)이 된다.
이러한 접근 방식은 n을 매번 2로 나눠 더 작은 문제로 만들어 해결하는 분할정복 방식이라고 할 수 있다.
분할 정복을 이용할 땐 n을 2로 나누는 과정에서 n이 1일 때, 다음 재귀함수에 들어가는 n은 0이 될 수 있으므로(즉, 1 // 2 = 0),
n이 0일 때 리턴해줄 값도 명시해준다.
🚀 정답 ⭕
import sys
MOD = 1000000007
# Rate of Increase
def RoI(x,y): # 초당 x배이고 y초가 주어졌을때 증가율
if y == 0:
return 1
res = RoI(x, y//2)
if y%2 == 0:
return (res * res) % MOD
else:
return (res * res * x) % MOD
if __name__=="__main__":
K,P,N=map(int, input().split()) # 바이러스의 수 K, 증가율 P, 총 시간 N(초)
res = RoI(P,N*10) * K # 증가율이 P일때 N*10초뒤 몇배가 되는지 계산후 K개의 바이러스를 곱해줌
print(res % MOD)
파이썬 거듭제곱 방법과
시간초과등을 고려하자…
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
