이 페이지는 checkup 1점, clear 10점, 미제거 셀 10000점이라는 비대칭 비용 구조가 왜 "블록 단위 존재 판정"을 강제하는지를 끝까지 따진다. culture()로 만든 누적 OR 접두값이 어떻게 한 번의 checkup으로 512칸의 세균 유무를 판정하는지, binary search가 첫 세균을 O(log SECT)에 특정하는 정당성을, 그리고 SECT=512라는 블록 크기 선택의 트레이드오프를 실제 통과 C++ 코드로 해부한다.
세균 문제의 점수표는 네 가지 비용으로 이루어진다: checkup 호출 1점, clear 호출 10점, 미제거 세균 셀 하나당 10000점, 그리고 실행시간 패널티. 이 비대칭이 베스트 해법의 모든 결정을 강제한다.
세 가지 사실을 먼저 못 박는다.
clear를 남발하면 안 된다 — 세균이 확실히 있는 칸에만 호출해야 한다. 빈 칸을 clear하는 것은 10점의 순손실이다.여기서 핵심 통찰이 나온다. 대부분의 칸은 비어 있다. 5천만 칸에 세균이 5만 개 — 밀도는 0.1%다. 999개의 빈 칸을 1개의 세균을 위해 한 칸씩 확인하는 것은 거대한 낭비다. 베스트 해법은 칸을 SECT=512짜리 블록으로 묶어, 블록 하나에 세균이 있는지 없는지를 단 한 번의 checkup으로 판정한다. 세균이 없으면 512칸을 통째로 건너뛴다 — 512칸의 비용이 checkup 1점으로 압축된다.
그런데 채점 시스템은 "구간에 세균이 있는가"라는 질의를 직접 제공하지 않는다. virus_checkup(n)은 한 칸의 값만 돌려준다. 그래서 베스트 해법은 시스템이 준 두 번째 함수 culture(n, a, b)를 이용해 구간 OR 집계를 스스로 만든다. 이것이 §3의 주제다.
이 풀이의 정확성은 단 하나의 사실 위에 서 있다: culture(n, a, b)가 tray[n] = tray[a] | tray[b]를 수행한다는 것. tray의 값은 0(빈 칸) 또는 1(세균)이므로, OR은 정확히 "둘 중 하나라도 세균이면 1"이라는 존재 판정 연산이다.
채점 배열 tray는 크기 MAIN_MAX*2다. 앞 절반 [0, LM)이 실제 검사 대상이고, 뒤 절반 [LM, 2·LM)은 풀이가 자유롭게 쓸 수 있는 작업 공간(scratch)이다. culture는 목적지 n이 반드시 뒤 절반에 있을 것을 요구한다(if (n < MAIN_MAX) return;) — 즉 작업 공간에만 쓸 수 있다. 풀이는 이 뒤 절반에 접두 OR 배열을 구축한다.
culture 루프가 블록 [s, e)를 다 처리한 직후, 작업 공간에 다음이 성립한다:
tray[LM + i] = tray[s] | tray[s+1] | … | tray[i] (모든 s ≤ i < e)
증명은 귀납이다. 기저: culture(LM+s, s, s)는 tray[LM+s] = tray[s] | tray[s] = tray[s] — 길이 1 접두 OR. 귀납: culture(LM+i, LM+i-1, i)는 tray[LM+i] = tray[LM+i-1] | tray[i] = (이미 성립하는 [s,i) 접두 OR) | tray[i] = [s,i] 접두 OR.
블록 [s, e)를 culture로 채운 뒤 virus_checkup(LM + e - 1) 한 번을 호출하면, 그 반환값은 정확히 "블록 [s, e) 안에 세균이 하나라도 있는가"다.
Invariant에 의해 tray[LM + e - 1]는 [s, e-1] 구간, 즉 블록 [s, e) 전체의 OR이다. OR은 "하나라도 1이면 1"이므로, 이 값이 1인 것은 블록 안에 세균 칸이 적어도 하나 존재하는 것과 동치다. 값이 0이면 블록의 모든 칸이 0 — 세균이 없다.
따라서 checkup 한 번으로 512칸의 세균 유무가 결정된다. 0이면 clear 없이 다음 블록으로 — 512칸이 checkup 1점에 처리된다.
블록에 세균이 있을 때만 안으로 들어간다. 이제 "블록 어딘가에 세균이 있다"는 것은 알지만, 어디인지는 모른다. 순진하게 s부터 한 칸씩 checkup하면 최악의 경우 512번이다. 베스트 해법은 binary search로 이를 O(log SECT)로 줄인다 — 그 정당성이 다음 보조정리다.
접두 OR 수열 P(i) = tray[LM+i]는 i에 대해 단조 비감소다. P(i+1) = P(i) | tray[i+1] ≥ P(i)이고, 값은 0/1뿐이므로 수열은 0 0 … 0 1 1 … 1 꼴이다.
0에서 1로 바뀌는 유일한 경계가 곧 블록 안 첫 번째 세균의 위치다. 단조 0/1 수열에서 경계를 찾는 것은 binary search의 교과서적 적용 — 중간점을 checkup해 1이면 경계가 왼쪽(또는 그 점), 0이면 오른쪽으로 좁힌다. O(log SECT)회의 checkup으로 첫 세균이 특정된다.
clear한 뒤, 다음 검사 구간의 시작을 그 세균 바로 다음 칸으로 재설정한다(e = retIndex + 1). 다음 루프 반복이 그 지점부터 새 블록을 만들어 다시 OR 판정하므로, 같은 블록의 나머지 세균은 후속 반복에서 자연히 잡힌다. 한 번에 하나씩, 그러나 빈 구간은 늘 통째로 건너뛴다.
test()는 검사 위치 s를 0부터 시작해, 블록을 만들고, 끝을 checkup하고, 세균이 있으면 안을 파고든다. 루프 갱신문이 s = e인 점에 주목하라 — e는 평소엔 블록 끝(s+SECT)이지만, 세균을 발견하면 retIndex+1로 줄어든다. 이 한 줄이 "세균 다음 칸부터 다시 시작" 로직을 담는다.
const int SECT = 512;void test() { int s, e; // 검사 구간 [시작, 끝) for (s = 0; s < LM; s = e) { culture(LM + s, s, s); // 접두 OR 기저: P(s)=tray[s] e = (s + SECT) < LM ? (s + SECT) : LM; // 블록 끝(꼬리는 절단) for (int i = s + 1; i < e; ++i) { culture(LM + i, LM + i - 1, i); // P(i)=P(i-1)|tray[i] } if (virus_checkup(LM + e - 1)) { // 블록 OR == 1 → 세균 존재 int retIndex = biSearchRecur(s, e - 1); clear(retIndex); // 첫 세균만 제거 e = retIndex + 1; // 다음 검사는 그 다음 칸부터 } // 세균이 없으면 e == s+SECT 그대로 → 512칸 통째 스킵 }}
culture(LM+s, s, s)는 OR 누적의 리셋 역할도 한다 — 새 블록의 접두 OR이 이전 블록 값을 물려받지 않도록 끊는다. (2) e는 변수이자 다음 시작점이다. 세균 발견 시 e = retIndex + 1로 줄어들고, s = e로 다음 반복이 정확히 그 지점부터 시작한다. (3) 세균이 없으면 e는 s+SECT 그대로라 — 다음 s가 512칸 건너뛴다. clear는 한 번도 호출되지 않는다.
이제 binary search다. Lemma가 보장하듯, 블록의 접두 OR 수열 P(s) … P(e-1)는 단조 0/1이다. biSearchRecur는 그 0→1 경계를 찾는다.
int biSearchRecur(register int low, register int high) { if (low >= high) return low; // 구간이 한 점 → 경계 확정 int mid = (low + high) / 2; if (virus_checkup(LM + mid)) // P(mid)==1 → 경계는 [low, mid] return biSearchRecur(low, mid); return biSearchRecur(mid + 1, high); // P(mid)==0 → 경계는 [mid+1, high]}
P(mid)==1이면 첫 1은 mid 이하이므로 high를 mid로, P(mid)==0이면 첫 1은 mid 초과이므로 low를 mid+1로. 구간이 한 점으로 줄면 그 점이 P가 처음 1이 되는 인덱스 = 첫 세균의 실제 칸 번호다(접두 OR이 0→1로 바뀌는 칸 = 세균 칸). 이 칸을 clear한다.
checkup 호출: 빈 블록은 checkup 1회. 블록 수는 LM / SECT ≈ 5×10⁷ / 512 ≈ 9.8×10⁴. 세균 있는 블록은 추가로 binary search O(log₂ 512) = 9회. 세균이 5만 개이므로 binary search 총비용 ~5×10⁴ · 9 ≈ 4.5×10⁵회. checkup 총합은 대략 ~10⁵ + 4.5×10⁵ ≈ 5.5×10⁵ — 순진한 전수 검사 5×10⁷보다 두 자릿수 적다.
clear 호출: 세균 칸 수와 같은 5×10⁴회 = 5×10⁵점.
culture 호출: 모든 칸이 정확히 한 번씩 OR 누적에 들어가므로 O(LM) = 5×10⁷. culture는 점수에 가산되지 않으나 실행시간에 기여한다 — 5천만 번의 단순 배열 OR은 -O2에서 수십 ms 수준이라 시간 패널티가 무시할 만하다.
블록 크기 SECT는 이 풀이의 유일한 자유 파라미터다. 너무 크게도, 너무 작게도 잡을 수 없다 — 두 종류의 비용이 반대 방향으로 움직이기 때문이다.
SECT가 너무 크면: 빈 블록 스킵의 효율은 좋아진다(블록 수가 줄어 checkup 1점짜리 스킵이 더 많은 칸을 흡수). 그러나 세균이 있는 블록에 들어갔을 때 binary search 깊이가 log₂(SECT)로 깊어진다. 세균이 5만 개이므로 깊이 1 증가는 곧 checkup 5만 회 추가다.
SECT가 너무 작으면: binary search는 얕아지지만(좋음), 블록 수가 폭증해 빈 블록조차 너무 많은 checkup을 소비한다. 극단적으로 SECT=1이면 블록 OR 판정이 곧 전수 검사 — 5천만 checkup으로 회귀한다. 게다가 블록마다 culture(LM+s, s, s) 리셋 호출이 한 번씩 더 들어가 culture 오버헤드도 커진다.
checkup ≈ LM/SECT + 5×10⁴·log₂(SECT)를 최소화하면, 첫 항은 SECT에 반비례하고 둘째 항은 거의 SECT에 무관(로그)하다. 따라서 SECT를 키울수록 첫 항이 빠르게 줄고, 512 근처에서 둘째 항(5×10⁴·9 ≈ 4.5×10⁵)이 첫 항(≈10⁵)을 넘어서며 추가 이득이 둔화된다. 512는 binary search 깊이가 깔끔히 9이고(2⁹), 빈 블록 checkup이 10만 수준으로 떨어지는 — 두 비용이 균형을 이루는 지점이다.
biSearchLoop(반복형)도 함께 들어 있으나, test()는 biSearchRecur(재귀형)를 호출한다. 깊이가 최대 9단계로 얕아 스택 부담이 없고, 재귀형 쪽이 "구간이 한 점이면 그 점 반환"이라는 종료를 더 명료하게 표현한다. 반복형의 low==high && ret<0 같은 경계 처리 분기가 재귀형에는 없어 읽기도 쉽다.
| 전략 | 완전 제거 | checkup 호출 | 구현 | 평가 |
|---|---|---|---|---|
| 전수 checkup + clear | 보장 | 5×10⁷ | 쉬움 | checkup 점수만 5천만 — 시간·점수 모두 탈락 |
| 블록 OR + 블록 내 선형탐색 | 보장 | ~10⁵ + 세균·256 | 쉬움 | 빈 블록 스킵은 좋으나 세균 블록 안이 O(SECT) |
| 전 구간 1회 OR 후 전체 binary search | 불가 | — | 불가 | 세균이 여럿이라 단일 경계가 없음 — 단조성 깨짐 |
| 블록 OR 스킵 + 블록 내 binary search | 보장 | ~5.5×10⁵ | 중간 | 빈 블록 통째 스킵 + 세균 블록 O(log SECT) |
표가 보여주는 구조는 명확하다. 완전 제거는 빈 칸을 끝까지 추적하는 전략이면 거의 공짜로 얻는다(Theorem 1·Lemma). 진짜 경쟁은 checkup 호출 수에서 벌어진다. 전수 검사는 5천만으로 즉시 탈락하고, "전 구간을 한 번에 binary search"는 세균이 여럿이라 접두 OR 수열의 0→1 경계가 단 하나가 아니어서 단조성 가정이 깨진다 — 그래서 반드시 구간을 블록으로 잘라 각 블록 안에서만 단조성을 회복해야 한다. 블록 OR 스킵으로 빈 영역을 무비용 통과하고, 세균 블록만 O(log SECT) binary search로 파고드는 조합이 두 자릿수 적은 호출 수를 만든다.
culture(LM+s, s, s)로 접두 OR을 다시 tray[s]에서 시작해야 한다. 이 기저 호출을 빼고 culture(LM+s, LM+s-1, s)로 이어 붙이면, 이전 블록의 누적 OR이 새 블록으로 새어 들어 — 빈 블록도 1로 판정돼 스킵이 무력화된다.
virus_checkup(LM + e - 1)을 읽어야 한다. checkup(e-1)로 원본 칸을 읽으면 그 칸 하나의 세균 유무일 뿐 — 블록 전체 OR이 아니다.
SECT의 배수가 아니면 마지막 블록은 512칸보다 짧다. e = (s+SECT) < LM ? (s+SECT) : LM로 끝을 LM에 묶지 않으면 culture가 [LM, 2LM) 범위를 벗어난 칸을 참조하려다 무시되거나 OR이 어긋난다.
clear한 뒤 e = retIndex + 1로 줄이지 않으면, 같은 블록에 남은 다른 세균이 다음 반복에서 재검사되지 않아 미제거로 남는다 — 셀당 10000점의 치명적 누수.
채점기 main은 10개 TC 각각에 대해 — 시드로 5만 개 세균을 배치하고, test()를 호출한 뒤, 남은 세균 셀을 직접 센다(if (tray[c] != 0) SCORE += 10000;). 이어 실행시간 패널티를 더하고, TC별 cut과 비교한다. 모든 TC가 cut 이하일 때만 PASS.
g++ -O2로 main.cpp + user.cpp를 함께 컴파일한다. 표준입력으로 각 TC의 seed와 cut을 (시드, 컷, 시드, 컷, …) 순으로 10쌍 준다. main이 각 TC의 SCORE를 누산해 모든 TC가 cut 이하면 PASS를 출력한다. 풀이가 모든 세균을 제거했다면 10000점짜리 미제거 항이 0이 되어, 점수는 checkup·clear 호출 수와 실행시간 패널티만으로 결정된다 — 이 페이지의 복잡도 분석이 곧 그 점수의 근거다.