제 2회 삼성 대학생 프로그래밍 경시대회 본선 후기(SCPC 2016)

대회는 크게 이벤트 세션과 본 대회로 구성되었다.

1. 이벤트 세션

오후 12시 ~ 12시 30분 동안 쉬운 영어 문제 하나를 푸는 이벤트가 있었다. 문제를 요약하면, N개의 나무가 있고 각각의 높이는 h(i)이다. 하루가 지남에 따라 모든 나무들은 길이가 1씩 자란다.  이 때, 각 날마다(매일) t(i) 높이에 레이저를 쏘아 높이가 t(i)를 넘는 나무들은 모두 t(i)가 되도록 자른다. 잘려지는 나무들의 길이의 총합을 구하는 것이 문제이다. O(N)의 간단한 풀이가 있지만, 문제를 보았을 때에는 O(N log N) 풀이를 떠올렸다. 하지만 맞추지 못하였는데, 문제를 푸는 시간 내에 Renumbering할 때의 배열 인자 부분에 코딩 실수가 있었던 것을 알아내지 못하였다. 이벤트 세션이 끝난 후, Data Maker와 Checker를 짜서 알아낼 수 있었다.

2. 본 대회

이벤트 세션 때에 코딩 실수가 있었기 때문에 바짝 긴장하고 시험을 보았다.

1번 문제는 전처리를 조금만 하면 되는 간단한 동적계획법 문제였다. 가 최소가 되는 는 임을 알면 쉽게 풀 수 있다. 10분 정도에 300점을 받았다.

2번 문제는 KMP를 N번 수행하고 N^2 동적계획법을 하면 되는 간단한 문제였다. 20분 정도에 맞추어 300점을 얻어 총점이 600점이 되었다. 이 때 등수가 2등이었다. 등수는 제출횟수가 같다면, 수행속도가 우선시 되기 때문에 실제로 맞춘 순서로 보면 6, 7번째로 2번을 풀었다.

3번 문제는 Daejeon Nationalwide Internet Competition 2014 I번과 거의 똑같은 문제였다. ICPC 대회 당시에도 저 문제를 코딩하였지만 맞추지 못하였는데, 이번에도 계속 0점을 받았다. 서브테스크 2까지는 확실히 나와야함에도 불구하고 5번 0점을 계속 받았다. 이 문제를 1시간 반 동안 붙잡다가 이러다간 안될 것 같아서 O(2^P*P*9)의 시간복잡도의 bitmask dp로 54점을 긁고 빠르게 4번으로 넘어갔다. 2시간 10분 쯤에 총점 654점이 되었던 것으로 기억하고 이 때 등수가 1등이었지만 20분 내로 10등 정도로 추락한다. 대회 시작 2시간 ~ 3시간 사이에 3번 만점자가 5명 정도 나오고, 54점을 패널티 없이 긁은 사람이 꽤나 많았던 것으로 기억한다.

4번 문제는 정해가 Parallel Binary Search인 어려운 문제이다. 당연히 대회 당시에는 해법을 떠올리지 못하고 서브테스크 3까지 긁으려고 하였으나 서브테스크 2까지는 1번에 맞추어 104점을 획득하였고, 어딘가 수식에서 오류가 났는데 고치지 못하였다. 따라서 대회가 끝날 때에 758점으로 마무리 하게 되었다.

대회 결과는 전체 등수가 16등이었고, 18등까지 수여하는 4등상과 함께 상금 200만원을 받을 수 있었다. 뭔가 아쉬움이 남는 대회였지만, 최소한으로 내가 얻을 수 있는 점수는 다 얻었기 때문에 후회는 없다. 좀 더 실력을 쌓는다면 3번을 최소한 서브테스크 2까지는 맞추고, 4번을 서브테스크 3까지는 맞출 수 있겠다. 사실 3번은 서브테스크 2까지 맞추면 만점 받는 게 그렇게 어려운 일은 아니지만... 

대회가 끝난 후, 시상식 이전에 추첨에서 갤럭시 기어핏2를 얻었다.

오랜만에 반가운 사람들도 많이 만나고, 만족할만한 결과를 얻을 수 있어 기분 좋은 대회였다.