[SUAPC 2024s 예비소집] 인생 첫 출제 후기

 

 

※ 주의: 이 글에는 문제 한요원의 잠입에 대한 스포일러가 들어있습니다. ※

첫 출제에 싱글벙글한 @minjunnick을 나타낸 그림이다.

서론

정말 많은 일들이 있었습니다. 결론부터 말씀드리자면, 저는 이번 SUAPC 2024 Summer에서 예비 소집에 제 인생 처음으로 문제를 하나 출제했습니다. 왜 본대회는 출제하지 않고 예비 소집만 출제했냐고 의문이 들 수도 있습니다. 묻는 것이 지극히 당연한 질문입니다. 출제할 거면 본대회에 하는 것이 더 좋을 것인데, 왜 예비 소집에 했는지 궁금할 것입니다. 이 모든 의문점을 이 글에서 풀어드리고자 합니다.

1. Call for Tasks

사실 원래 제 문제는 본대회에 출제 예정이었습니다. 우선 어째서 예비 소집으로 가게 된 것인가를 이야기하기 전, 잠깐 6월로 돌아가 제가 SUAPC 2024 Summer의 Call for Task를 처음 마주했을 때부터 지금까지, 제게 있었던 일들과 그 일들에 관한 생각들을 적어보고자 합니다. 가장 먼저, 저는 BOJ 1000솔을 찍고 출제를 하고 싶다는 생각이 넘쳐났습니다. 그러나 그 당시에 저는 출제를 할 수 있는 대회가 GEC-Cup밖에 없다고 생각했고, GEC-Cup에서는 제 연령대 때문에 출제보다는 참가에 집중하라는 선배들의 말씀에 저는 출제를 포기하는 듯했습니다. 하지만 그 꿈을 버리지 못했던 저는 solved.ac 디스코드에서 출제-검수-운영 탭을 돌아다녔고, 기어코 SUAPC 2024s Call for Task를 찾아버렸습니다.
 
처음에는 그저 단순한 호기심이었습니다. "Call for Task가 뭘까?" 하는 마음으로 읽어봤습니다. 그렇게 저는 Call for Task가 뭔지 알게 되었고, 굳이 본인 학교가 아니고 외부 출제자로 들어가는 경우에도, 학교에서 운영하는 대회이기만 하면 출제 조건 A만 만족해도 출제가 가능하다는 사실 또한 알게 되었습니다. 이 사실을 알게 된 저는 바로 문제 구상에 들어갔습니다.
 

2. 문제

저는 간단하게 풀 수 있는 다이나믹 프로그래밍 문제를 만들어야겠다고 생각했습니다. 그 당시 저는 빠져있던 게임이 하나 있었기에, 바로 그 게임을 모티브 삼아 문제를 제작했습니다. 그 문제가 바로 한요원의 잠입입니다. 모티브를 아시는 경우 이 문제와 원본 게임의 차이점을 알 수 있을 것입니다. 바로, 텔레포트가 생겼다는 것입니다. 문제를 다 만들고 보니 텔레포트가 없는 문제는 너무 쉽다고 생각했고, 매운맛을 추가하는 방법을 고안해 낸 끝에 텔레포트를 추가하게 되었습니다. 또한, 문제를 간단하게 유지하고 싶었던 저는 $N$의 제한을 $500$으로 설정하여 $O(N^3)$이 통과되도록 만들었습니다.
 
그렇게 저는 Call for Task에 제출했고, 거의 한 달 동안 답장이 오지 않길래 떨어졌나 싶었으나, 대략 마감일로부터 약 1달 후, 휴대폰에 문자가 하나 왔습니다.

 
저는 설레는 마음에 이메일을 열어보았고, 놀랍게도 문제가 선정되었다고 했습니다. 그렇게 저는 첫 출제를 SUAPC 2024s에 하게 된다고 생각했습니다.
 

3. 첫 번째 수정

가장 먼저 고쳐야 했던 것은 $O(N^3)$이었던 시간복잡도였습니다. 문제 선정자분들이 긴 시간복잡도를 마음에 들지 않아 했고, 최대 $O(N^2)$까지 낮춰달라고 하셨습니다. 그렇게 저는 시간복잡도가 낮은 풀이를 생각해 봤고, 결국 $O(N \log N)$까지 낮췄습니다. 정렬 한 번과 그리디, 그리고 우선순위 큐를 이용한 풀이였습니다. 저는 기쁜 마음에 제 코드를 MCS로 등록하고, 일정이었던 해외여행을 떠났습니다. 그 당시 저의 예상 난이도는 Gold III였습니다.
 

4. 두 번째 수정

문제는 해외여행에서 돌아온 후에 발생했습니다. 검수가 시작된 날이었습니다. 그날 저는 한 검수자분이 MCS가 잘못된 것 같다는 말과 함께 MCS의 반례를 찾아주셨습니다. 해외여행 때문에 너무 들떠서 그런가, 너무 어설프게 그리디를 짠 모양입니다. 그래서 저는 MCS를 수정하기 시작했습니다.
 
4일간 머리를 엄청나게 굴린 끝에, 결국에는 MCS를 고치는 데에 성공했습니다. 최종적으로 알고리즘 분류는 바뀌지 않았습니다. 정렬 한 번, 우선순위 큐와 그리디를 사용한 풀이였습니다. 그러나, 그리디 로직이 아주 많이 바뀌었습니다. MCMF를 토대로 그리디를 증명해야 했으며, 이때 제 예상 난이도는 Diamond V였습니다. 그러나, 한요원의 잠입의 저주는 아직 끝나지 않았습니다.
··

5. 유사성 문제

사실 검수가 시작되었을 때도 한 번 언급이 되었었는데, 그때에는 별로 유사하지 않은 것 같다고 다른 검수자분이 말씀하셔서 계속 진행했었습니다. 그러나, 대회 1주일 전, 이 문제와 유사한 문제였던 AGC018 기출문제가 다시 언급되며, 정확히 같은 코드를 작성한 뒤 단지 4줄만 바꾸면 AC가 난다는 충격적인 사실이 확인되었습니다. 한요원의 잠입이 대회에서 난도가 높은 문제 중 하나였기 때문에 복사 붙여넣기로 풀리는 경우 최종 순위에 치명적인 영향을 줄 것이라는 의견이었습니다. 이렇게 한요원의 잠입은 SUAPC 2024s에서 완전히 제외될 뻔했습니다. 다행스럽게도 예비 소집으로 보내자는 의견이 나왔고, 그 의견에 대부분이 동의하여 한요원은 예비 소집으로 보내지게 되었습니다.
 

6. 데이터 업로드 문제

예비 소집 시작 당일, 예비 소집에서도 제외될 뻔했습니다. (나한테 왜 그래요 진짜) 8월 23일 저녁, 예비 소집 하루 전, 어떤 이유에서였는지는 몰라도 BOJ Stack에 데이터가 업로드되지 않는 버그가 있었습니다. 그때 저는 정답이 가능한 정답 중 최댓값인 경우를 저격하는 데이터를 업로드하고 있었습니다. 저는 자고 일어나면 데이터가 업로드될 것이라는 믿음과 함께 잠에 들었습니다. 하지만, 8월 24일 오전 8시, 데이터는 아직도 업로드 되어있지 않았습니다.
 
그날 아침, 저는 데이터의 개수를 원래 225개였던 것을(...) 100개 미만으로 해달라는 요청을 받았고, 이에 따라 모든 데이터를 날리고 아예 새로 생성된 데이터를 넣었습니다. 하지만 데이터는 오전 9시까지 업로드될 기미를 보이지 않고, 결국 대회의 주최자이자 ICPC Sinchon의 회장이신 이지언 님께 부탁해 예비 소집을 당일 오후 5시까지 미루는 것에 성공했습니다.
 
하지만 저는 안심할 수만은 없었습니다. 만약 오후 5시까지 데이터가 올라가지 않는다면 예비 소집에서 한요원의 잠입은 빼고 진행하는 것이 최선일 것 같다고 말씀하셨고, SUAPC 2025w 예비 소집 문제로 쓰여야 할 것 같다는 것이었습니다. 이렇게 허무하게 첫 출제일이 미뤄지나 싶었을 때, 다행히 12시 22분쯤 BOJ Stack이 정상화되었고, 데이터가 무사히 업로드되었으며, 테스트 결과도··· 정상적으로 나와야 했었으나, 당연히 "맞았습니다!!"를 받아야 할 코드들이 갑자기 전부 "틀렸습니다"를 토해내는 대참사가 벌어졌었습니다. 사건의 전말은 마지막 데이터의 출력이 다른 데이터의 출력과 섞여버려서 일어난 해프닝이었습니다. 그렇게 오후 12시 40분경, 테스트까지 마무리하면서 예비 소집은 다시 오후 2시로 당겨졌고, 무사히 한요원의 잠입은 백준에 등장할 수 있었습니다.
 

결론

첫 출제 경험이어서 그런지 아니면 평소에도 출제자들은 이렇게 스릴 넘치는 삶을 살고 있는 건지 모르겠지만, 여러 의미로 즐거웠던 첫 출제 경험이었습니다. 이번 SUAPC 2024 Summer에 출제하신 모든 출제자분과, 검수자분들, 그리고 운영진분들께 수고하셨다는 말 올립니다. 다음 SUAPC 2025 Winter를 기약하며...