[파이썬] Softeer 연습문제 #4. 수퍼바이러스 (Lv. 3) 완벽해설

문제

 

https://softeer.ai/practice/6292

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

해설

 

https://vehiclewithai.tistory.com/4

Softeer 연습문제 [파이썬] #1. A+B 해설

(우선 입력값을 받아들이는 기초적인 부분에 대한 내용은 위에 있으니 참고해주시면 감사하겠습니다!)

 

처음에는 입력값을 받아들이고, 그 입력값을 토대로 계산만 해주면 되는 문제로 알았다.

 

그래서 처음에 K마리가 있고,

슈퍼바이러스가 0.1초당 P배씩 증가하기 때문에 K에다가 0.1초마다 P를 한번씩 곱해주는 연산을 진행하면 되고, 마지막에 1000000007로 나눈 나머지(%)를 구해주면 된다고 생각을 했는데,

 

import sys

# 입력값 받기
K, P, N = map(int, sys.stdin.readline().split())
# 계산해주기 (pow: 제곱해주는 함수, %: 나눗셈의 나머지 구해주는 연산자)
print(K*pow(P, N*10)%1000000007)

 

그렇게 푸니 2초가 초과해서 오답이 되는 경우가 생겨서 이 문제를 통과하지 못했다.

 

알고보니 단순 계산이 아니라 효율을 높이기 위해 "지수

재귀함수"라는 알고리즘을 사용해야만 했던 것이었다.

 

즉 제곱항의 계산을 재귀적으로 표현해주게 되면 그 연산량이 줄어들기 때문에 2초 안에 풀 수가 있게 된다. (고 하는데,,, 왜 여전히 오답이 뜨는지 모르겠다.)

 

 

 

코드

 

import sys

def power(num, power_term):
  if power_term==1:
    return num%1000000007
  
  if (power_term%2 == 0):
    sub1 = power(num, power_term/2)
    return sub1*sub1%1000000007
  else:
    sub2 = power(num, (power_term-1)/2)
    return num*sub2*sub2%1000000007
    
# 입력값 받기
K, P, N = map(int, sys.stdin.readline().split())
# 계산해주기 (pow: 제곱해주는 함수, %: 나눗셈의 나머지 구해주는 연산자)

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

 

결과