이번 겨울 방학에 2023 ICPC Sinchon Winter Algorithm Camp Contest에 참가하여 1등(금상)을 했다.
방학 동안 열심히 공부하기도 했고 이제 초급 알고리즘은 많이 익숙해졌다고 생각해서 높은 등수가 나올 것이라고 예상은 했지만 1등까지 할 줄은 못했다. 물론 그날 컨디션도 좋았고 운도 많이 따라주었다고 생각한다.
문제 : https://www.acmicpc.net/category/801
해설 : https://www.acmicpc.net/board/view/111865
대회는 12시부터 5시였다. 평소 같으면 대회 시작하기 전까지 푹 자고 일어나서 밥을 먹고 대회를 했을 것 같지만 이 날 아침 9시에 선릉역 근처에서 삼성 SDS Pro SW 검정 시험이 있었어서 일찍 일어났다. 아침부터 코딩하느라 대회 때 피곤하지는 않을까라는 걱정을 했었지만 오히려 머리가 잘 돌아갔던 것 같다. 이상하게 긴장이 하나도 되지 않았고 이 날 SW 검정 시험을 잘 치르고 나왔던 상태라 자신감도 가득 차있었다.
9시부터 11시까지 SW 검정 시험을 마친 후 간단하게 민석이(neveralone)와 점심을 먹고 근처 스터디카페에 가서 대회 준비를 했다. 스터디 카페에 우리밖에 없었고 집중이 잘 되는 분위기였어서 스터디 카페를 간 것도 좋은 선택이었던 것 같다. 이번 대회에서 좋은 성적을 거두고 기세를 몰아 1주일 뒤에 열리는 SUAPC까지 잘 보자라는 마인드로 팀원인 민석이(neveralone), 영현이(yhnoh8623)와 파이팅을 외치며 대회를 시작했다.
대회 타임라인
[00:05] AC (First Solve)
문제를 보자마자 $O(N)$ 풀이가 떠올라서 코드를 짜다가 생각보다는 시간이 걸렸다. 대회를 시작하기 전에는 페널티 관리를 목표로 코드를 다 짠 것 같아도 바로 제출하기보다 좀만 더 고민해 보자고 다짐했지만 막상 코드를 짜니까 제출을 안 할 수가 없었다. 제발 맞아라 기도를 하며 제출을 했더니 다행히 AC를 받았고, 스코어보드를 확인해 보니 First Solve여서 기분 좋게 대회를 시작할 수 있었다.
B. 만다라트 만들기
[00:39] AC
간단한 구현 문제였지만 처음 문제를 봤을 때 한숨부터 나왔다. 개인적으로 문제가 긴 것을 선호하지 않는데 조건이 너무 많기도 했고 이해하는 데도 좀 오래 걸렸다. 처음 코드를 짜고 예제를 비교해 봤는데 답이 다르게 나와서 문제를 다시 읽어보니 조건 하나를 놓쳐서 처음부터 다시 코드를 짜느라 시간이 오래 걸렸다. 다시 코드를 짜고 제출을 했는데 다행히 한 번에 AC를 받았다. 풀이는 사람마다 다르겠지만 나는 생각보다 간단하게 구현을 한 것 같다. 너무 시간을 오래 쓴 것 같아 스코어보드를 보니 4등으로 밀려나 있었다. 이때 조금 마음이 급해졌던 것 같다.
C. 발머의 피크 이론
[00:54] AC (3WA)
개인적으로 아쉬운 문제이다. 누적 합을 이용하는 간단한 슬라이딩 윈도우 문제여서 보자마자 풀이가 떠올랐다. B번에서 마음이 조급해졌던 게 화가 되었다. 반례는 생각도 하지 않고 바로 제출을 했는데 34프로에서 WA를 받았다. 절대 틀릴 리 없다고 생각했어서 당황했다. 코드가 틀렸다는 것을 의심하지 않고 정답이 int형 범위를 벗어나지 않는다는 것을 알고 있으면서도 혹시 모른다는 생각에 정답을 long long int형으로 바꾸어 제출을 해보았지만 결과는 똑같이 WA였다. 다시 마음을 잡고 반례를 생각해 보았다. L이 N보다 클 수도 있구나라는 걸 깨닫고 조건을 추가하여 다시 제출을 했지만 역시나 WA였다. (지금 와서 보니 L이 N보다 작다는 조건이 있다...) 이때 멘탈이 좀 흔들렸던 것 같다. 흔들리는 멘탈을 잡으며 문제를 처음부터 정독하며 직접 몇 개의 테스트 케이스를 시험해 보았다. 생각보다 쉬운 곳에서 내가 실수를 했다는 것을 깨닫고 코드를 다시 짰다. 다행히 이번에는 AC를 받을 수 있었다. 문제를 풀고 스코어보드를 보니 D번까지 푼 사람도 꽤 있었고 등수가 많이 밀려있었지만 멘탈을 바로 잡았다.
D. 알파벳 블록
[01:30] AC (1WA 1RTE)
스코어보드에서 C번은 나처럼 많이 틀린 사람이 있었고 D번은 한 번에 맞힌 사람이 꽤 있어서 별로 어렵지 않구나라고 예측했고 문제를 봤더니 실제로 문자열과 덱을 이용한 간단한 문제였다. 코드를 짜면 짤수록 뭔가 이상한 길에 빠져들고 있구나라는 걸 느꼈지만 예제가 잘 돌아가고 반례도 없는 것 같아서 제출을 했는데 WA도 받았고, 한 번은 덱이 빈 것을 생각하지 않고 RTE도 받은 후에 AC를 받을 수 있었다. 나는 개인적으로 A, B, C, D 중에 가장 어렵다고 생각한 문제였는데 대회가 끝나고 대화를 해보니 D가 가장 쉽다는 의견이 많았다. 민석이(neveralone)는 메모리 초과로 무수한 억까를 당했다고 한다...
E. 연애 혁명
[02:11] AC
D번을 풀고 난 후 집중력이 살짝 떨어졌고 스코어보드를 보니 벌써 E번까지 푼 사람이 2명이나 있었다. 그중 한 명이 영현이(yhnoh8623)여서 그런지 뭔가 승부욕이 다시 타올랐다. 화장실을 한 번 다녀온 뒤에 책상에 앉아서 차분히 문제를 읽었다. 처음에는 그리디와 DFS를 이용한 풀이를 생각했었는데 단순한 MST 문제라는 것을 깨달았다. 코드를 다 지운 후 크루스칼 알고리즘을 조금 변형하여 코드를 다시 짜고 제출을 했더니 AC를 받았다. 이때까지만 해도 3등이었는데 나보다 먼저 E를 푼 2명 모두 F를 풀지 못하고 있는 것을 보았다. 그래서 아 수상은 하겠구나 그리고 F를 풀면 어쩌면 1등을 할 수 있을지도?라는 생각을 했다.
F. 레이저 쏘기
[03:25] AC (First Solve)
문제를 읽어보니 역시 만만치 않았다. 뭔가 알고리즘이 있는 것이 아니라 수학 문제를 푸는 것 같았다. 아이패드에 수학 문제를 풀듯이 풀이를 계속해서 생각해 보았다. 뭔가 규칙이 있을 것 같아서 이것저것 다 생각해 보았고 어쩌다가 규칙을 하나 발견했다. 이렇게 처음 생각한 풀이가 모든 레이저에 대해서 모든 기울기를 비교하는 것이었는데 이 풀이는 $O(N^{2})$이었다. 근데 입력을 1만으로 잘못 보아서 어떻게 시간을 줄이지?를 고민하다가 문제를 다시 읽었다. 근데 입력으로 주어지는 N과 K가 최대 1000이었다! 그래서 바로 $O(N^{2})$ 풀이로 구현을 했고 map과 유클리드 호제법을 이용하였다. 코드를 짜고 예제와 내가 생각한 케이스가 잘 돌아가는 것을 보고 한 번에 바로 맞을 거라는 생각보다는 몇 퍼에서 틀릴까라는 생각으로 제출을 했다. 채점이 정말 천천히 됐다. 거의 30초 가까운 시간 동안 1퍼센트부터 차근차근 채점이 됐다. 퍼센트가 올라갈수록 설마 이게 맞아?라는 생각으로 지켜보았고 결국 한 번에 AC를 받았다. 이때 스터디 카페에서 소리를 지를 뻔했다. 스코어보드 프리즈까지 아무도 F를 풀지 못했었는데 와 진짜 1등 하나?라는 기대감이 이때부터 조금씩 생겼다.
[05:01] 1WA
기세를 몰아 마지막 문제까지 맞히고 싶었다. 마지막 문제는 DP가 나오겠구나 예상했는데 역시나 DP였다. 문제 자체는 롤을 하는 사람들은 모두 재밌다고 느낄 수 있는 문제이지만 풀이 자체는 너무 재미없었다. 비교적으로 DP 문제에 취약한 나는 배열도 여러 개 만들고 조건도 여러 개 설정하면서 어떻게든 풀어보려고 애썼다. 와 너무 어렵다... 어떻게 푸는 거지라는 말만 되풀이하면서 코드를 계속 짰다. 예시조차도 돌아가지 않다가 어느덧 대회가 5분이 남아있었다. 마지막 2분쯤 남았을 때 갑자기 어? 이렇게 하면 안 되나?라는 생각으로 미친 듯이 타자를 치고 예시가 돌아가는 것까지 확인한 후 제출을 하려 했지만 이미 대회가 종료되어 있었다. 아 10초만 있었다면...이라는 아쉬움이 남았지만 대회가 끝난 후에 제출해 보았는데 바로 틀려버렸다.
이렇게 대회가 종료되고 스코어보드 공개 전까지 민석이(neveralone)와 영현이(yhnoh8623)는 어떻게 됐는지 계속 이야기했다. 둘 다 E까지는 풀었다고 했고 영현이(yhnoh8623)는 F를 10트했는데 틀렸다고 했다. 이때 진짜 1등 할 수도 있겠다는 기대감이 더욱 커졌다. 떨리는 마음으로 스코어보드를 보았고 6솔 하신 분이 계셨지만 페널티로 1등을 차지할 수 있었다! 아직 온 길은 너무 짧고 가야 할 길은 많이 남아있지만 중간에 그동안 공부한 것에 대한 1차 보상을 받았다는 느낌이랄까... 행복했다. 민석이(neveralone)와 영현이(yhnoh8623)도 각각 9등, 4등으로 다들 좋은 결과를 받아서 더 기분이 좋았다.
일주일 뒤에 있는 SUAPC도 이 기세를 몰아 잘 치를 수 있을 것 같았다. (그렇게 망했다고 한다...ㅎ)
다음 방학 때는 중급 contest에 참가해 볼 예정인데 그때에도 좋은 결과가 있길 바란다. 아니면 초급 강사를 한 번 도전해 볼까라는 생각도 막연하게 가지고 있는데 기회가 된다면 해보고 싶기도 하다. 그동안 많은 코태기가 있었는데 이번 기회를 통해서 ps에 좀 더 흥미를 느낄 수 있었고 꾸준히 하면 된다라는 생각으로 많이 노력해야겠다...! 파이팅!
끝으로 캠프와 대회 잘 운영해 주신 운영진분들께 고생하셨다고 말씀드리고 싶다. 감사합니다!! :D