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

문제 확인

Softeer

• 사이트를 방문하여 문제를 확인해주세요.

나의 풀이

시간 초과가 발생하여 결국 풀이를 참고해서 풀었다.

 

처음엔 바이러스가 곱해지는 비율(거듭 제곱)을 빠르게 구하기 위해서 O(logN)의 시간 복잡도를 가지는 분할 정복을 사용했다. 하지만 N의 범위가 1,000,000이라서 분할 정복 여부는 시간 초과가 관계가 없었다. 결국 큰 수 끼리 곱해지는 과정에서 시간 초과가 발생하게 되는데 큰 수를 어떻게 처리해야할 지 몰랐다.

 

처음 분할 정복을 시도한 풀이는 다음과 같다.

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

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)

참고 풀이

A와 B의 곱을 Q로 나눈 나머지는 A와 B를 각각 Q로 나눈 뒤 계산한 나머지와 같다.

증명은 다음과 같다.

https://www.youtube.com/watch?v=RwPEFIW1p8c

import sys

virus_num, p, time = map(int, input().split())
# 나머지 성질 이용
for _ in range(time):
    virus_num *= p
    virus_num %= 1000000007
print(virus_num)