[python] 소프티어 - 바이러스

소프티어 level 2 문제
https://softeer.ai/practice/info.do?idx=1&eid=407

아래 처럼 짰더니 시간초과가 뜨는 TC가 있었다

virus, rate, n = map(int, input().split())

for i in range(n):
    virus = virus * rate

print(virus%1000000007)

문제가 최종 바이러스 개수를 1000000007로 나눈 나머지를 출력하라. 였기때문에 바이러스가 1000000007 이상되면 break를 시켜보았다.

virus, rate, n = map(int, input().split())

for i in range(n):
    virus = virus * rate
    if virus > 1000000007:
        break

print(virus%1000000007)

시간초과는 없지만 오답이 생겼다.

그런데 1초에 1억 번 연산인데 n이 최대 100만이니까 시간초과는 안뜰건데... 뭐가 문젤까

결국 해설을 봤다
https://softeer.ai/class/algotutor/detail.do?id=63
오버플로우가 발생해서 그렇다.

GPT에게 내 코드를 줘봤다.

chatGPT
... 그러나 이 코드에는 문제가 있습니다. 바이러스의 증가율(rate)이 10^8 이상일 수 있고, 총 시간(n)도 10^6 이상일 수 있습니다. 이 경우, 위 코드에서 사용한 방법은 오버플로우가 발생할 수 있습니다. 따라서 바이러스의 증가율을 반복적으로 적용하는 방식보다는 지수 연산을 사용하는 것이 더 안전하고 정확합니다.

아래는 바이러스 개수 계산에 지수 연산을 활용한 수정된 코드입니다:

virus, rate, n = map(int, input().split())

result = (virus * pow(rate, n, 1000000007)) % 1000000007

print(result)

위의 코드는 주어진 시간(n) 동안 바이러스 개수를 계산하고 최종 바이러스 개수를 출력합니다. pow(rate, n, 1000000007)는 rate를 n번 곱하고 1000000007로 나눈 나머지를 계산합니다. 이를 처음 바이러스 개수(virus)에 곱하고 1000000007로 나눈 나머지를 최종 결과로 출력합니다.

해설에서는 이런 이유로 각 곱마다 나눈 나머지와 다 곱하고 나눈 나머지의 값이 값다고 설명한다.

보기에는 간단한 문제였는데 오답률이 높은 데는 이유가 있었다.

제약 조건도 잘 봐야겠다. 힌트가 될 수 있다.

1초당 연산량 : 1억

$10^8$ : 1억,
$10^6$ : 100만

파이썬 int 오버플로우 : 약 21억 ...

바이러스 증가량이 최대 1억이니까 조치를 취하지 않으면 오버플로우 난다는 생각을 해야한다 ! !!

다음 처럼 수정해서 성공했다.

virus, rate, n = map(int, input().split())

for i in range(n):
    virus = virus * rate
    virus = virus % 1000000007


print(virus%1000000007)