2016년 SCPC(삼성 대학생 프로그래밍 경진대회)에 참가했다. 올해로 2회를 맞는 젊은 대회인데, 국내 대회임에도 불구하고 구글 코드잼 같은 유명 세계대회를 뛰어넘는 엄청난 규모의 상금으로 유명하다. 작년에는 미국에 있었고 온라인 예선도 까먹고 안 쳐서 주변에 상금 받은 사람들을 보면서 부러워 했었는데 올해는 기회가 돼서 본선에 참가했다.

대회 시작은 오후 1시였는데 대회장 내부에 간단하게 체험 부스 등이 준비되어 있어서 미리 와서 이벤트에 참가하는 것을 권장하더라. 포토존이나 간식거리, 체험 게임 등 이벤트로서의 준비는 굉장히 잘 되어 있었는데, 대회로서의 준비는 아무래도 경험이 적어서 그런지 아쉬운 부분이 눈에 띄었다. 대회장 내부에 음료 반입 금지라든지, 대회 시작 전 컴퓨터가 열려 있어서 미리 코드를 짜 놓는 방식의 부정행위가 가능할 것 같다는 걱정도 있었고, 채점은 g++로 하면서 로컬에는 MSVC만 깔려 있다든지 이것저것 있었다.

풀이

연습문제 – Lumbering

이벤트 문제로 영어 문제가 나왔다. 문제 자체는 간단했는데 가장 먼저 푼 사람에게만 상품을 주기 때문에 이것 때문에 괜히 빨리 풀어야 한다는 생각에 사로잡혀서 그냥 푸는 것보다 오래 걸렸다. (자르는 높이 – 자르는 시간)이 가장 작은 도끼질 시간을 찾아서, 모든 나무를 그 도끼질 한 번으로 자른다고 생각하면 된다. 처음에는 스택이나 인덱스트리 쪽으로 생각했는데 그럴 필요가 전혀 없었다.

A – 재활용

Simple DP. 시작 위치와 끝 위치를 고정했을 때 쓰레기통을 하나 놓아서 거리가 최소화 되게 하는 지점을 로 전처리 한 뒤 이 배열을 사용해 DP를 돌리면 된다. 예선 2차 1번에서 제한 조건으로 같은 라도 커팅을 해야만 통과가 되도록 시간제한을 약간 빡빡하게 줬었던 기억이 나서 최대한 불필요한 테이블 계산을 줄이려고 노력했다. long long을 쓰지 않아 한 번 WA를 받았다.

B – 랩뮤직

B에서 삽질을 좀 오래 한 편이다. 전날 했던 벼락치기의 부작용 때문에 생각이 어려운 방향으로 흘러가서 Suffix Array도 짜고 LCP도 구하다가 깨달음을 얻고 BFS + KMP로 빠르게 풀었다. 반복문을 N까지 돌아야 되는데 N-1까지 돌아서 틀리는 등의 실수도 좀 해서 시간이 상당히 걸렸다.

C – 폭격

B를 풀고 시간이 두 시간 약간 넘게 남았다. C랑 D를 읽어봤는데 D는 생각도 어렵고 코드 짜는 게 너무 오래 걸릴 것이라 판단돼서 C를 잡았다. KOI 기출인 두부 모판 자르기랑 비슷한 문제인데 비트 DP가 아니라 3진수 DP를 해야 하고, 리넘버링도 해야 하고, 그냥 돌리면 느려서 큐를 사용해 최적화를 하면 풀리는 문제다. 해야 할 것들은 명확하지만 그걸 짜기가 어려운 유형의 문제. 어떤 y가 입력됐을 때 y-1, y, y+1 셋을 모두 추가하면 리넘버링 후에도 단순 격자 위에 있다고 생각할 수 있다는 걸 관찰해 코드의 복잡도를 줄일 수 있었다.

사소한 오타 등의 실수는 있었지만 전체 코드 설계는 처음부터 부드럽게 진행된 문제였다. 이건 벼락치기의 도움을 받았다고 생각하는데, 내가 공부해간 알고리즘들을 직접적으로 쓰는 문제는 없었지만 잘 짠 예제 코드들을 보다가 가서 설계를 잘 한 게 아닐까 생각하고 있다.

풀고 나니까 시간이 20분 정도 남았는데, D 부분점수를 노리기에도 시간이 빠듯해 그냥 C 푸는 사람이 적기를 기원하며 새로고침 누르면서 시간을 때웠다. 내가 C를 6번째로 풀었는데, 마지막에 C를 푼 사람이 7명밖에 되지 않아 안심하며 3등상을 예상하고 있었다.

뒷풀이

대회 끝나고 나서는 미니 토크 하고, 경품 추첨 하고, 설문조사 등을 하다가 시상식을 했다. 미니 토크에서는 시간제한이 적다고 말이 많았던 2차 3번에 대해 교수님이 풀이해 주셨는데, 말이 많았던 이유가 같은 풀이임에도 불구하고 통과가 되는 풀이가 있고 아닌 풀이가 있었기 때문이지만 “호호 여러분들 엔제곱 풀이를 생각하셨나 봐요” 같은 투로 말씀하셔서 여기서도 대회측이 참가자들의 여론을 잘 파악하지 못하고 있다는 것을 느꼈다. 설문조사에 이런 부분을 담으려고 노력했지만 잘 전달되었는지는 모르겠다.

경품 추첨에서는 운 좋게 기어 360을 받았다. 시계나 태블릿을 원했다. 참가만 해도 기계식 키보드를 주는데다가 상금도 많고 이벤트로 뿌린 경품도 많았다. 역시 삼성은 돈이 많다. 시상식에서는 대회 때 예상한대로 4~8위에게 주는 3등상을 받았다. 대회 나가기 전 예상으로 실수를 좀 하면 5등상(~38위), 평타 치면 4등상(~18위) 정도 받겠다고 생각했는데 예상보다 좋은 성적을 거두어 기분이 좋았다. 상 등급이 하나씩 오를 때마다 상금이 최소 두 배로 뛴다. 1등상은 요새 핫하신 dotorya님이 2천만원 받아가셨다.

사진 찍고 수상자 인터뷰 하고 짐 찾아서 아는 사람들이랑 고기 먹고 끝났다. 내일은 전대프연이 있는데 아마 이 사람들 대부분이 다시 나타날 것이다.