[파이썬] Softeer 연습문제 #12. 바이러스 완벽해설

문제

 

https://softeer.ai/practice/6284

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

 

 

 

해설

https://sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)

 

모듈러 산술을 알 때 이 문제를 풀 수가 있다.

 

간단하게 표현하자면

(A+B)%C = ((A%C) + (B%C))%C

(A-B)%C = ((A%C)  -  (B%C))%C

(A*B)%C = ((A%C)*(B%C))%C

if (A%C) = (B%C), then (A^k % C) = (B^k % C)

위의 사칙연산의 모든 조건이 만족한다는 뜻이다.

 

이 모듈러 연산은 코딩에 있어서 메모리 사용량을 아끼는데 사용할 수가 있다.

 

그리고 마침 이 소프티어 바이러스 문제는 이 모듈러 연산을 사용해서 메모리를 줄여야 하는 특별한 예시이기도 하다.

 

 

이 문제의 조건으로 "256MB"이하를 사용하도록 주어져 있다. 그리고 여기서 "최종 바이러스 개수를 10000000007로 나눈 나머지를 출력하라" 라고 요구조건이 주어졌다.

 

만약 직접 하나하나 곱하는 식으로 계산한다면 제곱이 되는 값이 1억을 넘어가는 값일 경우 메모리를 엄청나게 차지하여 쉽게 256MB를 넘길 것이다.

 

따라서 이 문제를 해결하기 위해선

 

 

"K*P^N을 10000000007로 나눈 나머지"를 "P^(N/2) % 10000000007"로 쪼개주는 것으로 시작해,

이를 계속 가장 단순한 방법까지 쪼개면

 

 

결국 각각의 P를 10000000007로 나눈 나머지를 하나하나 곱하는 방식으로 단순화시킬 수 있게 된다. 이렇게 되면 숫자가 커져서 생기는 메모리 과다를 대폭 줄일 수 있게 된다.

 

 

코드

 

import sys

K, P, N = map(int, sys.stdin.readline().split())
virus = K
for _ in range(N):
  virus *= P
  virus = virus % 1000000007

print(virus)

 

 

 

결과