[Softeer] 바이러스 (level 2)

사용 언어: Python3

문제

바이러스

풀이

내 풀이

import sys
# 처음에 K마리
# 1초당 P배씩 증가
# N초 후에는 총 몇 마리?

def DFS(L, res):
    if L == N + 1:
        print(res % 1000000007)
    else:
        DFS(L+1, res*P)

K, P, N = map(int, input().split())

DFS(1, K)

• 시간 초과

내 풀이

import sys

K, P, N = map(int, input().split())

res = K
for _ in range(N):
    res *= P
print(res)

• 시간 초과

다른 풀이 - 1

import sys

K, P, N = map(int, input().split())

res = K
for _ in range(N):
    res *= P
    res %= 1000000007 # ✅ 매계산마다 1000000007로 나눈다.
print(res)

• 정답!

다른 풀이 - 2

import sys

K, P, N = map(int, input().split())

res = K
q = 1000000007
for _ in range(N):
    A = res % q
    B = P % q
    res = (A*B) % q
print(res)

• 정답!
• input이 최대 10^8이기 때문에 단순 연산만으로도 시간 초과를 일으킬 수 있는 것이 함정이다.
  • 연산의 나머지는 나머지들의 연산임을 활용해서 해결할 수 있다.
    
  • 🌟 (A*B) % q는 (A%q)*(B%q) % q와 같다!
• 참고
  • 블로그
  • 강의

0510 추가

import sys

K, P, N = map(int, input().split())

res = K
q = 1000000007
for _ in range(N):
    res = (res%q)*(P%q)%q
print(res)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기