루미 알고리즘

#1197브론즈전염병학Epidemiology

CCC 2020코딩주니어 2번영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문을 루미 알고리즘이 한국어로 옮겼습니다. 뜻이 다르면 원문이 맞습니다. (검수일 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명보다 많은 사람이 병에 걸린 적이 있습니다.

채점 데이터와 풀이는 그 해 문제 전체가 한 묶음입니다. 받으면 이 문제의 것만이 아니라 2020년 대회 전체가 들어 있습니다.

자료

출처 표기

출처: Centre for Education in Mathematics and Computing (CEMC), University of Waterloo 2020년 · 원문 페이지 · 이용 조건 CC BY-NC 4.0 · 부문별 문제지 한 권에서 해당 문제 부분을 보여 줍니다. 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.