Notion에 남아 있던 글을 문장과 수식 위주로 다듬어 복원했다. 대회는 2025년 10월 11일 열린 ICPC 서울 지역 예선이다.
팀 결성
CP를 겨우 재활 중이던 나였기에 원래는 참가할 계획이 없었다. 친한 후배 lumitt에게 연락이 오기 전까지는.
이후 ad-hoc과 case work에 강한 mint09가 합류하면서 본선 진출을 노릴 만한 팀이 만들어졌다.
| 팀원 | 주 역할 |
|---|---|
lumitt | 구현, well-known |
mint09 | ad-hoc, case work |
PastelRain | 수학, DP |
본선에 가더라도 수상까지 이어질 가능성은 높지 않다고 봤다. 그래도 팀의 전력과 대회 경험을 생각하면 참가할 가치는 충분했다.
나는 A번 quick solving에 자신이 있어 앞 문제부터 보기로 했다. lumitt은 뒤에서부터 훑으며 쉬운 문제를 찾기로 했다.
대회 당일의 악재
시작하기 전부터 계획은 많이 무너져 있었다.
mint09가 가족여행으로 자리를 비워 실제 경기는 두 명이 치렀다.- 사전에 팀 노트를 인쇄할 공간을 찾지 못해 팀 노트 없이 시작했다.
- 전날 사용하기로 한 내 노트북이 고장 났다.
lumitt의 노트북은 macOS였고, C++를 쓸 수 있는 익숙한 IDE가 없었다. CLion 사용법도 몰라 나는 반강제로 Python을 사용했다.
대회가 시작되기 전부터 한 명과 한 대의 노트북, 익숙한 언어를 잃은 셈이었다.
시간순 기록
0:00–0:20
A를 보자마자 \(\mathcal{O}(N)\) 스위핑으로 풀 수 있을 것 같아 구현해 제출했지만 실패했다. 더 붙잡지 않고 lumitt에게 넘겼다.
lumitt은 F와 I가 쉬운 문제라는 것을 발견했다. F를 한 번의 WA 뒤 빠르게 해결하고 I를 나에게 전달했다.
I를 계산하던 중 나는 어떤 값에 4를 곱하는 치명적인 실수를 했다. 그 오류 때문에 정해를 찾지 못했고, 나이브한 구현으로 찍맞을 시도했지만 실패했다. 실제로는 정답에 거의 도달해 있었다.
0:20–1:00
lumitt이 A의 \(\mathcal{O}(N^2)\) DP 풀이를 찾아 한 번에 AC를 받았다.
그동안 나는 남은 문제의 난이도를 훑었다. C, H, J가 그나마 해볼 만하다고 보고 나머지를 배제했다. I가 계속 풀리지 않아 J를 잡았지만, 내가 아는 알고리즘 안에는 정해가 없다고 판단했다. 핵심 관찰만 정리해 lumitt에게 넘겼다.
1:00–1:30
H를 같이 의논하던 중 lumitt이 풀이를 알아냈다. 나도 2년 전에 비슷한 BOJ 23035를 풀었다는 사실을 떠올렸다.
다만 구현법은 잊은 상태였다. 구현을 기억하는 lumitt에게 H를 맡기고 다시 I로 돌아갔다.
종이에 적은 계산을 다시 보다가 4를 곱했던 오류를 발견했다. 식을 바로잡자 풀이가 명확해졌고, 기존 코드를 일부 수정해 I를 해결했다.
1:30–2:20
lumitt이 H의 세그먼트 트리 스위핑 구현을 완성했다. 테스트케이스도 통과했지만 제출 결과는 시간 초과였다.
lumitt은 Python 자체의 속도가 원인이라고 판단해 나에게 C++ 구현을 부탁했다. 나는 같은 로직을 넘겨받아 포팅을 시작했고, 그동안 lumitt은 C에 집중했다.
2:20–3:00
대회 종료를 얼마 남기지 않은 시점, 10분이 넘는 포팅 끝에 C++ 구현을 완성했고 H에서 AC를 받았다.
lumitt은 C의 풀이도 알아냈지만, 남은 시간 안에 많은 조건 분기를 구현하는 것은 불가능하다고 판단했다. 더 건드리지 않고 경우의 수와 페널티를 계산했다.
문제별 복기
F — lumitt
Codeforces A번에 가까운 구현 문제였다. 한 번의 WA 뒤 해결했다.
A — lumitt
\(\mathcal{O}(N^2)\) DP 문제였다. 나는 처음 생각한 스위핑 풀이가 실패한 뒤 넘겼고, lumitt이 올바른 점화식을 찾아 구현했다.
I — PastelRain
간단한 수학 문제였다. 계산 실수를 찾는 데 1시간이 걸렸다. 그 사이 정답에 가까운 찍기 풀이를 제출했지만 맞지 않았다. 오류를 고친 뒤의 구현은 매우 짧았다.
어려운 수학을 몰라서 늦어진 문제가 아니라, 종이에 적은 상수 하나를 의심하지 않아 늦어진 문제였다.
H — PastelRain, lumitt
좌표계를 \(-45^\circ\) 회전하면 \(\mathcal{O}(N\log N)\) 세그먼트 트리 스위핑 또는 LIS로 풀 수 있는 최단 경로 문제가 된다.
나는 유사 문제를 푼 기억으로 방향을 확인했고, 구현을 기억하던 lumitt이 Python 코드를 작성했다. 시간 초과가 난 뒤 lumitt의 부탁을 받아 10분 넘게 C++로 옮겨 통과시켰다.
대회가 끝난 뒤 원인을 다시 확인했다. 문제는 Python이 아니라 Fast I/O를 적용하지 않은 것이었다. lumitt은 언어의 속도 문제로 오인했고, 정작 내가 새로 쓴 C++ 코드에는 fast I/O가 들어가 통과했다.
결과
두 명이서 4문제, 458분 페널티, 전체 52위를 기록했다. 점수만 보면 본선 진출권에 들어갈 성적이었다.
하지만 팀은 mint09의 여행 일정을 사전에 운영진에게 알렸고, 관리자가 이를 출결에 반영했다. 세 명이 모두 참가해야 한다는 규정 때문에 결격 처리되어 본선 명단에는 들지 못했다.
코드와 점수로는 선을 넘었지만 참가 자격에서 멈췄다. 대회 전에 이미 알린 사정이었기에 더 허탈했다.
대회가 끝난 뒤
여행에서 돌아온 mint09에게 대만 우산과 파인애플 과자를 받았다. 파인애플 과자는 잘 먹었고, 우산은 2026년 7월인 지금까지도 잘 쓰고 있다.
따져 보면 우리가 본선에 가서 얻을 수 있었던 상금의 기댓값보다 선물값이 더 비쌌다. 그런 의미에서는 한편으로 다행이라고 생각한다.
그래도 돈과 커리어는 다른 문제였다. 본선 진출이라는 기록을 얻지 못한 아쉬움은 남았다. 예선에서 실제로 본선권 성적을 만들었기에 더 그랬다.
잘한 점
- 한 명이 빠지고 장비까지 고장 난 상황에서 두 명이 4문제를 해결했다.
- I의 계산 오류를 끝내 찾아 정답으로 바꿨다.
- H의 시간 초과 원인을 당시에는 정확히 찾지 못했지만, 요청받은 C++ 포팅을 10분 넘게 밀어붙여 마감 전에 AC로 바꿨다.
- 풀 문제와 버릴 문제를 계속 갱신해 52위까지 끌어올렸다.
오답 노트
참가 규정은 실력과 별개의 첫 번째 문제다
팀원이 현장에 없다는 사실을 운영진에게 미리 알렸더라도, 그것이 참가 자격을 보장하지는 않았다. 출결 조건처럼 결과를 무효로 만들 수 있는 규정은 문의에 그치지 않고 답변과 적용 방식을 문서로 확인해야 했다.
계산 실수는 직관으로 찾지 못한다
I에서 풀이의 핵심은 거의 맞았지만 잘못 곱한 4 하나 때문에 1시간을 잃었다. 수학 문제에서 결과가 어긋날 때는 아이디어 전체를 갈아엎기 전에 각 줄의 상수와 경계값을 독립적으로 검산해야 한다.
대회 환경은 전날에 고정한다
노트북, IDE, 언어와 팀 노트가 모두 당일 변수가 되었다. C++ 포팅 능력으로 H를 살렸지만, 처음부터 익숙한 환경이었다면 같은 시간을 다른 문제에 쓸 수 있었다.
시간 초과는 언어를 바꾸기 전에 I/O부터 확인한다
H는 Python이라서 느린 문제가 아니었다. Fast I/O가 빠진 것이 원인이었다. 언어를 통째로 바꾸는 선택은 비용이 크다. 시간복잡도, 입력량, I/O와 상수 시간을 먼저 확인했어야 했다.
댓글과 반응
GitHub 계정으로 로그인해 의견을 남길 수 있습니다. 반응과 답글은 GitHub Discussions에 이어집니다.