바이러스 제거

서브태스크 1: 감염된 구역의 집합을 비트마스크로 표현한다. 가능한 세 구역의 조합을 모두 선택하고, 제거 후 자정의 동시 전파를 적용한 상태로 간선을 만든다. 모든 구역이 감염된 상태에서 감염 구역이 없는 상태까지 BFS를 수행하고 경로를 복원한다. 비트 연산으로 전이를 계산하면 시간 복잡도는 $O(2^N N^3)$, 공간 복잡도는 $O(2^N)$이다. 아래 구성으로 항상 $N$일 이내에 끝낼 수 있으므로 BFS로 찾은 최단 경로도 일수 제한을 만족한다.

전체 풀이: $X=N-2$로 정하고, $k$일째 정오에 $1,k+1,k+2$번 구역의 바이러스를 제거한다 ().

$N=3$이면 첫날에 모든 구역을 제거한다. $N>3$일 때, $1 \leq k \leq N-3$에 대해 일째 자정 이후 깨끗한 구역은 정확히 이다. 첫날 정오에는 이 깨끗해지고 자정에 양 끝이 다시 감염되어 번만 남는다. 귀납적으로, 직전의 깨끗한 구간 에 를 더하면 정오에는 가 깨끗해진다. 자정에는 바깥의 감염 구역에 인접한 양 끝만 다시 감염되어 이 남는다.

마지막 $N-2$일째에는 남은 $1,N-1,N$번 구역을 제거하므로 모든 구역이 깨끗해지고 더는 전파가 일어나지 않는다. 출력하는 세 번호는 항상 서로 다르고 $1$ 이상 $N$ 이하이다. 사용 일수 는 이하이다.

시간 복잡도는 출력 크기에 비례하는 $O(N)$, 출력 버퍼를 제외한 추가 공간 복잡도는 $O(1)$이다. 채점기는 각 날의 상태를 직접 시뮬레이션하며 $O(NX)$ 시간과 $O(N)$ 공간을 사용한다. 이므로 전체 시뮬레이션은 최대 개의 구역 갱신으로 처리된다.

Solution written by GPT