Goodbye, BOJ 2025! Open Contest 후기

2025년 12월 27일에 진행한 Goodbye, BOJ 2025! Open Contest에 참가했습니다. 3문제를 풀어 전체 참가자 129명 중 20등을 했습니다. (3솔 중에서는 1등입니다. 왜지) 아래 내용에는 문제에 대한 스포일러가 있으니 주의 바랍니다. 또한, 문제 난이도는 모두 2025.12.28 오후 1시 45분 기준입니다.

A. 2026년이 기대되는 이유 (+1)

푼 시각: 0:05
종료 후 문제 번호: 35030
종료 후 문제 난이도: S1

첫 문제입니다. 문제가 예상 난이도 순으로 정렬되어 있으므로, 자연스럽게 가장 쉬운 문제이기도 합니다. 예상 난이도가 실버 상위권인 것치고는 어렵지 않았습니다. 풀이는 다음과 같습니다.

1. 에라토스테네스의 체로 적당한 범위의 자연수 (저는 $10^6$까지 했습니다) 전체를 소수 판정 해 줍니다.
2. 브루트 포스를 이용해 각 수가 특별한 수인지 확인합니다.
3. 누적 합을 통해 가능한 모든 $N$에 대해 답을 저장합니다.
4. 쿼리마다 바로 답을 출력합니다.

D. 용사 (-2)

제출한 시각: 0:22, 0:31
종료 후 문제 번호: 35033
종료 후 문제 난이도: G1

B와 C를 건너뛰고 바로 D로 갔습니다. 사실 B와 C를 보기는 했는데, 둘 모두 어려워 보여서 넘어갔습니다. D는 트리에서의 애드 혹 문제인 것 같아 잡아 보기로 했습니다. 제가 생각했던 풀이는 다음과 같습니다.

1. 1번 정점에서 시작하여 DFS를 돕니다.
2. 각 정점에 대하여, 더 이상 들어갈 자식이 없다면 그 값을 출력하고 함수를 벗어납니다.

그러나 제가 간과한 반례가 있었습니다. TTTTTTTTTTT와 같은 트리에서 (맨 왼쪽이 루트입니다) 아래로 내려가는 부분을 먼저 탐색하게 된다면, 낙인의 개수가 $O(N)$이 되어 실패하게 됩니다! 그렇게 2틀을 박고, C로 도망쳤습니다.

C. 마왕 (+1)

푼 시각: 0:52
종료 후 문제 번호: 35032
종료 후 문제 난이도: G2

$\frac{1}{9}$이라는 수가 가장 먼저 눈에 띕니다. 또한 한 지점이 둘 이상의 마법진에 속하면 안 된다는 조건이 있습니다. 여기에서 아래와 같은 그리디를 생각해 내었고, Proof by AC로 통과했습니다. 어떤 마법진이 있을 때, 그보다 작거나 같고 초기 마법진과 영역을 공유하는 다른 마법진을 활용해 영역을 최대한 넓이더라도 초기 마방진의 $9$배를 넘길 수 없다는 관찰에 기반합니다.

1. 방문하지 않은 마법진 중 가장 큰 마법진을 선택하고, 방문 처리합니다.
2. 1에서 선택한 마법진과 공유하는 영역이 있는 마법진을 모두 방문 처리합니다.
3. 모든 마법진을 방문할 때까지 1~2를 반복합니다.

D. 용사 (+3)

푼 시각: 2:00
종료 후 문제 번호: 35033
종료 후 문제 난이도: G1

D번에 다시 돌아왔습니다. B를 푼 뒤에 오고 싶었지만, 끝까지 풀지 못했습니다. 그래서 D를 다시 잡기 시작했고, 얼마 지나지 않아 앞서 소개한 반례를 찾았습니다. 그래서 조건을 조금 바꿨고, AC를 받을 수 있었습니다.

1. 1번 정점에서 시작하여 DFS를 돕니다.
2. 정점 $u$에서 정점 $v_i$의 재귀 호출을 끝냈을 때, $v_i$를 루트로 하는 서브 트리의 깊이와 $v_i$의 번호를 pair로 저장하여 정점 $u$에 대한 우선순위 큐에 넣습니다.
3. DFS를 다시 한번 도는데, 서브트리의 깊이가 깊은 것부터 탐색합니다.

저는 우선순위 큐를 사용했지만, 정렬을 사용하면 훨씬 간결하게 구현할 수 있습니다.

끝

B번을 다시 잡아 봤지만, 결국 풀지 못하고 대회가 끝났습니다. B는 업솔빙을 해봐야겠네요. 곧 12월 BOJ 풀이 기록이 올라갈 것 같습니다. 많은 관심 바랍니다!