SWERC 2016 팀 연습 복기글

처음으로 1컴으로 연습을 해보기로 하였다. 선정한 대회는 SWERC 2016. 

복기글을 너무 늦게 써서 한 행동들만 기억나고 그 순서가 기억이 나지 않는다. 

ABCD를 류트, EFG를 클리멕, HIJK을 내가 보기 시작했다. 초반 부분은 잘 기억이 나지 않는다. 가장 크게 느꼈던 점은 영어 실력의 부재. 코포에서 아래의 힌트 부분과 번역기가 얼마나 큰 역할을 했었는지 새삼 깨달을 수 있었던 시간이었다.문제를 해석하는 것이 어질어질 했고, 문제들이 하나 같이 해석하고나서도 막막했다. C와 F가 가장 많이 풀리고 있었고, 류트와 클리멕이 C와 F를 같이 의견을 나누면서 하나씩 풀어내었다. 아마 류트가 C, 클리멕이 F를 했던것으로 기억한다. 나는 그 사이에 그 다음 많이 풀린 K를 류트에게 소개하였다. 문제설명과 조그마한 아이디어를 던져주고 D를 고민했다. 
C : AC (00:20)
F : AC (00:42)

 나는 H가 최적화 빡구현 이라고 생각을 했다. n차원 파스칼에서 바닥에 나오는 모든 수의 종류를 출력하는 문제였다. 나는 top-down dp 에서 최대한 적은 상태만 탐색하도록 최적화를 하는 문제라고 생각했다. 하지만 vector를 set에 담는 등의 방법을 생각했고, 이를 H를 잡으려고 하는 클리멕에게 설명했다. 
 둘 다 확신이 없었던 부분은 시간. 아무리 최적화를 한다고 해도 재귀를 탐색하는 부분이 많으며 한 번 탐색에 처리해야할 양도 적지 않았다. 그렇기 때문에 클리멕은 확실히 다른 방법이 있을 것이라고 생각했고, 나는 더이상 떠오르지 않아 계속 D를 고민했다. 

 류트는 K코딩. 클리멕은 식을 발견했다. 파스칼 바닥 수가 어떠한 식으로 표현되는 수들이 나온다는 것을 발견했으며, 그 식을 돌면서 계산하면 문제를 풀 수 있게 되었다. 나도 보자마자 맞다고 생각했고, 류트가 K를 마무리하고 이어서 바로 클리멕이 코딩을해서 맞았다. 
K : AC (01:21)
H : AC (01:36)

 클리멕이 K를 코딩하는 사이 내가 생각하던 D에 진전이 없어 보였다. 그래서 다른 것을 보려고 했고, E를 보려고 했다가 문자열이라서 바로 튀었다. 그리고 B를 읽어보았다. 푼 사람수는 적었지만 류트가 문제를 설명해줬는데 되게 할만해보였다.
 숫자쌍에서 바로 좌표계를 캐치해냈고, 문제를 잘 전환 시켜보니 주어진 특정 점을 지나는 기울기 음수의 직선을 그어 왼쪽 아래 반평면에 있는 점의 개수의 최댓값과 최솟값을 구하는 문제였다. 가능한 직선은 다른 점을 지나는 직선들이었고, 기울기에 따라서 스위핑을 하면 될 것으로 보였다. 
 하지만 기하였고, 난 절대 자신이 없었다. 바로 류트를 불렀고, 기하 구현을 잘하는 류트가 풀이 마무리 부터 AC까지 맡게 되었다. 

 계속 고민하다가 내가 내린 D의 결론은 오차범위를 이용하는 풀이였다. 
1. 직접 시뮬레이션을 시간제한까지 여러번 돌려서 평균 값을 구한다. 
2. DP를 적절히 해서 각 라운드별로 기댓값을 구하며, 그 기댓값이 오차범위보다 작아지는 지점까지만 DP를 돌린다. 
라운드의 최대치가 70정도가 될 것 같아서 나온 결론이었다.

 클리멕이 두 가지 가정을 보더니 2번이 굉장히 끌린다고 했다. 그리고 얼마 지나지 않아 클리멕이 DP에서 가장 중요한 '가능한 상태' 를 추려왔고, 그것을 듣고 내가 DP 식을 마무리 지었다. 나는 남은 A,E 중 문자열인 E를 포기하고 A를 보러 갔고 클리멕이 D를 코딩해서 맞았다. 그리고 얼마 지나지 않아 류트가 B를 맞아왔다. 다들 구현을 어케하는건지... 특히 기하를 구현할 수 있는 사람이 있어서 다행이라고 생각했다. 
D : AC (02:21) 
B : AC (02:57)

 클리멕이 E를 잡고 나는 기하가 가능한 류트를 믿고 A를 잡고 있었다. 식을 세웠는데 생각보다 깔끔한 관찰로 쉽게 코딩이 가능할 것 같았다. 내 풀이를 듣고 류트도 새로운 풀이를 하나 만들었고, 둘 다 O(N)의 풀이었기 때문에 N<=20 인 제한에 의문을 품었다. 일단 각자 풀이를 각자 코딩하는 것이 맞다는 결론을 나왔고 그 대신 서로 코딩하는 것을 옆에서 봐주는 것으로 하였다. 그와 중에 클리멕도 E에 대한 풀이가 거의 나온것으로 보였고, 일단 A부터 해결하기로 하였다. 

 기하를 구현하는 것은 굉장히 새로운 경험이었다. 신경 쓸 것도 많았고, 모든 연산에 새로운 틀을 끼우는 느낌이었다. 그렇게 다 코딩을 하던 도중에 반례가 생각났다... 류트의 풀이는 반례가 없는 것 같아서 바로 류트에게 바톤 터치를 했다.

 다년간의 훈수 경험 때문인지 정작 나는 잘 코딩을 못하면서 옆에서 코딩 하는 것을 보면서 오타는 쏙쏙 잘 찾아낸다. 그렇게 열심히 코딩을 하고 끝나기 전에 제출을 해보았지만 WA를 받고 끝나게 되었다.

 그날 집에서 클리멕은 E를 완성하고 나와 류트는 A의 오타와 풀이 오류를 찾아내었다. 

첫 팀연습 치고는 나쁘지 않은 결과라고 할 수도 있지만, 그리 썩 기분 좋지 않은 결과 인것 같기도 하다. 내가 붕 뜨는 시간이 생각보다 길었고, 아무래도 전체적으로 1컴에 익숙하지 않은 것도 크게 작용했던 것 같다. 일단 내가 구현을 무조건적으로 맡기지 말고 구현실력을 좀 끌어올려야 겠다는 강력한 다짐을 했다.

아무튼 다음을 기약하며...