[Softeer / Level2] 바이러스

https://www.softeer.ai/practice/info.do?idx=1&eid=407 

Softeer

---

 

 

너무 오랫만에 맞닥뜨린 시간초과가 나는 문제여서 당황했다.

개인적으로 파이썬은 시간초과 카운팅하기가 너무어렵다.

 

처음에는, print((K * (P ** N)) % 1000000007)으로 풀었다. 아니나 다를까 시간초과

내장함수를 찾아서 쓰면 더 효율적이지 않을까 싶어서 공식문서를 뒤져보고 power함수를 쓰기로 마음먹었다.

 

기본 파이썬 내장함수인 pow로 1000000007를 마지막 인자로 던져주면 직접 나눠주는 것보다 더 효율적이라고 한다.

그러나, 마지막에 K 곱해주고 한번 더 디비전 연산을 해주어야 한다. (시간초과는 안나지만 깔끔하지 않아서 철수)

 

결국엔, for 문 돌려가며 시간만큼 연산한 값을 늘려나가는 방식으로 만들었다.

<나의 풀이>

import sys

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

for i in range(N):
    K = (K * P) % 1000000007

#print((K * pow(P, N, 1000000007)) % 1000000007)

print(K)

 

 

<다른 사람 풀이>

제네릭한 풀이 케이스를 알아보기 위해 다른사람의 풀이를 참고했다.

 

다른 사람 풀이에서는 Divide and conquer으로 짝수, 홀수로 나누고 재귀를 타서 시간 복잡도를 낮췄다. (공간 복잡도는 올라가겠지만)

import sys
 
def get_pow(a, b):
    if b == 0:
        return 1
    # b가 짝수일 경우
    elif b % 2 == 0:
        return get_pow(a, b // 2) * get_pow(a, b // 2)
    # b가 홀수일 경우
    else:
        return get_pow(a, b // 2) * get_pow(a, b // 2) * a
 
virus_num, p, time = map(int, input().split())
print(virus_num * get_pow(p, time) % 1000000007)

https://only-wanna.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%86%8C%ED%94%84%ED%8B%B0%EC%96%B4-%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4

[파이썬] 소프티어 바이러스

https://m.blog.naver.com/sunbi5252/221977857377

[ 파이썬 알고리즘 ] 4. 분할 정복