PCR 검사 풀링

면접 대비

시간 제한1초메모리 제한1024 MB

요약

한 사람이 양성일 확률 p가 주어졌을 때, 사람 한 명당 검사 횟수의 기댓값이 가장 작은 풀 크기 N(2에서 16 사이)을 구합니다. 그런 N이 없으면 1을 출력합니다.

문제

PCR(중합효소 연쇄 반응) 검사는 DNA 시료를 반복해서 복제한 뒤, COVID에 특이적인 DNA 조각이 있는지 확인하는 검사이다. 시간이 오래 걸리고 필요한 시약의 양도 제한되어 있을 수 있다. 처리량을 높이는 방법 가운데 하나가 시료를 모아서 검사하는 풀링이다.

핵심 아이디어는 N명의 시료를 섞고, 섞은 시료에 PCR 검사를 한 번 하는 것이다. 검사 결과가 음성이면 추가 검사는 필요 없다. 양성이면 N명 모두를 개별적으로 다시 검사해야 한다. 양성일 확률이 낮으면 필요한 검사 횟수가 크게 줄어든다.

한 사람이 양성일 확률 p를 입력받아, 함께 섞을 시료의 최적 개수 N을 출력하는 프로그램을 작성하라.

N명 모두가 음성일 확률을 P라고 하면, 필요한 검사 횟수의 기댓값 E(T)는 다음과 같다.

$E(T) = 1 \cdot P + N \cdot (1 - P)$

E(T) / N이 최소가 되도록 N을 고른다.

예를 들어 N이 2이고 p가 0.5이면 P는 0.25이고, $E(T) = 0.25 + 2 \cdot 0.75 = 1.75$ 이다. 이는 N보다 조금 작을 뿐이다.

각 사람의 시료가 충분하다는 것을 보장하려면 N은 16을 넘을 수 없다.

입력은 한 줄로 이루어지며, 0 < p < 1을 만족하는 실수 p가 주어진다. p는 한 사람이 COVID 양성 판정을 받을 확률이다.

출력은 한 줄이며, 하나의 10진수 정수를 출력한다. 모든 N에 대해 $E(T) \geq N$ 이면 1을 출력한다. 그렇지 않은 경우에는 E(T) / N을 최소로 만드는 N의 값을 출력하며, 이때 $2 \leq N \leq 16$ 이다.