§ 1문제 정의
culture(n,a,b)는 두 셀의 OR 결과를 새 셀에 적는다. 이를 이용해 구간의 “이 안에 세균이 있는가”를 한 번에 묻고, 있다면 이진탐색으로 좁힌다.
512칸씩 묶어 누적 OR을 후반 절반(LM..2LM)에 누적한다. 구간 끝의 OR이 1이라면 그 구간 안에 세균이 있다 — 이제 이진탐색으로 정확한 위치를 찾고 clear. 0이라면 구간 전체를 통과.
이로써 5천만 번 클리어 대신 5만 번의 이진탐색만 필요하다. checkup 호출 수가 SCORE를 결정한다.
‘어디?’를 5천만 번 묻지 말고, ‘이 512칸 안에 있어?’를 10만 번 물어라.
§ 2예제 시각화 — 32칸 배열, 3개 세균
FIG. 6 — section sweep + binary search per hit
STEP 01 / 8
SPACE play/pause · ← → step · R reset
§ 3알고리즘 골격
test():
SECT = 512
s = 0
while s < LM:
culture(LM+s, s, s) # 구간 시작값 백업
for i in s+1 .. s+SECT-1:
culture(LM+i, LM+i-1, i) # 누적 OR
end = min(s+SECT, LM)
if virus_checkup(LM+end-1): # 구간 안에 세균 ?
idx = binarySearch(s, end-1) # 정확한 위치 찾기
clear(idx)
s = idx + 1 # 다시 같은 구간을 처음부터
else:
s = end # 통과