영어 원문을 루미 알고리즘이 한국어로 옮겼습니다. 뜻이 다르면 원문이 맞습니다. (검수일 2026-11-19)
전염병학
원제: Epidemiology
문제
전염병학(epidemiology)을 연구하는 사람들은 질병이 퍼지는 모습을 분석하려고 모형을 사용합니다. 이 문제에서는 간단한 모형을 사용합니다.
어떤 사람이 병에 걸리면 그 사람은 정확히 R명의 다른 사람을 감염시키는데, 병에 걸린 바로 다음 날에만 감염시킵니다. 두 번 이상 감염되는 사람은 없습니다. 병에 걸린 적이 있는 사람이 모두 합쳐 P명보다 많아지는 때가 언제인지 알아내려고 합니다.
(이 문제는 지금의 코로나바이러스 유행이 일어나기 전에 만들어졌습니다. 우리는 이 병과 다른 질병들 때문에 지금 전 세계의 많은 사람이 겪고 있는 고통을 잘 알고 있습니다. 이 시기에 이 문제를 싣는 것이, 실제 세상의 문제를 푸는 데 컴퓨터 과학과 수학이 맡는 중요한 역할을 잘 보여 주기를 바랍니다.)
입력
입력은 세 줄입니다. 각 줄에는 양의 정수가 하나씩 있습니다. 첫째 줄에는 P의 값이 주어집니다. 둘째 줄에는 0일째(Day 0)에 병에 걸려 있는 사람의 수 N이 주어집니다. 셋째 줄에는 R의 값이 주어집니다. P ≤ 10 000 000 이고 N ≤ P 이며 R ≤ 10 이라고 가정합니다.
출력
병에 걸린 적이 있는 사람의 수를 모두 합한 값이 처음으로 P보다 커지는 날의 번호를 출력합니다.
예제
예제 1
750 1 5
4
0일째에 병에 걸려 있는 1명이 1일째에 5명을 감염시킵니다. 2일째에는 정확히 25명이 감염됩니다. 3일째에는 정확히 125명이 감염됩니다. 4일째가 끝날 때까지 병에 걸린 적이 있는 사람은 모두 1 + 5 + 25 + 125 + 625 = 781명이고, 781 > 750 입니다.
예제 2
10 2 1
5
0일째에 병에 걸려 있는 사람은 2명입니다. 그 뒤로는 날마다 정확히 2명이 감염됩니다. 4일째가 끝날 때까지 병에 걸린 적이 있는 사람은 모두 정확히 10명이고, 5일째가 끝날 때에는 10명보다 많은 사람이 병에 걸린 적이 있습니다.