문제 개요
빠르게 증식하는 위험한 바이러스가 있다고 가정해 봅시다. 매 시간마다 바이러스 세포 수가 x배 증가할 확률은 0.5이고, y배 증가할 확률 역시 0.5입니다. 처음에 바이러스가 단 하나의 세포로 시작했다면, t시간 후의 기대 바이러스 세포 수를 계산해야 합니다. 만약 결과값이 너무 커진다면 10^9+7로 나눈 나머지를 구하면 됩니다.
예를 들어 입력이 x = 2, y = 4, t = 1이라면 출력은 3이 됩니다. 초기에는 바이러스가 한 개의 세포만 가지고 있으며, 0.5의 확률로 크기가 2배(x2)가 되고, 나머지 0.5의 확률로 크기가 4배가 됩니다. 따라서 t = 1일 때의 기대 세포 수는 다음과 같습니다.
0.5 × 2 × 1 + 0.5 × 4 × 1 = 3
해결 접근 방법
두 배율이 각각 0.5의 동일한 확률로 발생하므로, 한 단계당 성장 배율의 기댓값은 (x + y) / 2입니다. 결국 t시간 후의 기대 세포 수는 ((x + y) / 2)^t와 같습니다.
다만 t가 클 경우 지수 연산을 그대로 수행하면 값이 기하급수적으로 커지기 때문에, 모듈러 거듭제곱(분할 정복 기반의 빠른 거듭제곱) 기법을 활용해야 합니다. 이 방식은 O(log t)의 시간 복잡도로 거듭제곱을 효율적으로 계산할 수 있습니다.
구체적인 해결 단계는 다음과 같습니다.
- m = 10^9+7
- factor := (x+y)//2 — 성장 배율의 평균값
- res := 1
- t > 0인 동안 반복:
- t가 홀수이면 res := (res * factor) mod m
- factor := (factor * factor) mod m
- t := t // 2
- res 반환
예제 코드
아래 구현 예시를 통해 더 잘 이해해 봅시다.
m=10**9+7
def solve(x, y, t):
factor=(x+y)//2
res=1
while t > 0:
if t % 2:
res = (res*factor) % m
factor = (factor*factor) % m
t = t// 2
return res
x = 2
y = 4
t = 1
print(solve(x, y, t))
입력
2, 4, 1
출력
3