IUPC 2020 참가 후기

3등했다.

어제 교내 프로그래밍 경시대회인 인하대학교 프로그래밍 경진대회 2020이 끝났고, 만족스러운 결과를 얻었다.

 

팀원은 ICPC 팀원 그대로 하려고 했는데, 팀원 중 한 명이 탈주하는 바람에 급하게 나머지 한 명을 구했다. 그래서 나와 yooshnn, sh0705k가 한 팀이 되었다. 나랑 yooshnn은 잘 아는 사이지만, 새로 구한 팀원은 우리 둘이랑 아예 모르는 사이였다. 그래서 대회 전에 했던 몇 번의 팀 연습을 통해 친해지려고 노력했다. 팀명은 "인덕이 팬클럽"으로 결정했다.

 

이번 대회는 shake!의 예선전이기도 해서, 3위 안에 들어 몇 주 뒤 있을 shake!에도 참가하고 싶었다. 출전권이 상위 세 팀에게만 부여되기 때문이었다. 하지만, 너무 강력한 우승 후보인 "인하인의 피아노 사랑"이 있었고, 다른 팀들도 강력할 것이라고 예상했기 때문에 정말 3등 안에 들 수 있을지 굉장히 불확실했다.

 

 

Timeline

 

시작 전

IUPC의 최근 출제 경향을 보면, 출제되는 12문제의 문제들 중 절반 정도는 문제를 보자 마자 풀이를 알 수 있는 쉬운 문제들로 구성되어 있고, 정말 시간을 많이 투자해야 하는 킬러 문제가 한 문제 있었다. 따라서, 올해도 비슷한 기조를 이을 것이라고 생각했고, 다른 팀원들이 앞쪽의 쉬운 문제들을 푸는 동안, 내가 문제들을 한번 쭉 훑으며 바로바로 풀이가 나오는 문제들을 먼저 밀고 오겠다고 했다. 하지만 이는 잘못된 생각이었다.

 

00:03 A AC

00:11 B AC

먼저, 팀원들은 앞쪽 문제들부터 보면서 쉬운 문제를 밀어주었다.

 

00:31 E AC

문제들을 대충 한 번 씩 훑어보았지만 작년만큼 문제가 쉽지 않았다. 그래서 너무나도 자명한 3차원 dp 문제인 E 구현을 시작했다. 풀다가 문제를 다시 읽어 보니 높이가 2인 선인장이 무조건 있어야 한다고 해서 4차원 dp로 바꾸어 문제를 해결했다. yooshnn은 H가 트라이를 이용하는 문제 같다고 하면서 H를 풀러 떠났다.

 

00:39 D TLE

E를 풀고 나는 비교적 많이 풀린 J의 문제 해석을 하고 있었고, sh0705k가 시간 복잡도를 잘못 계산해서 D TLE가 한번 나왔다.

 

00:54 ~ 01:23 J WA

나는 J번 문제가 전혀 이해가 되지 않았고, 출제진에게 질문을 했다. 하지만, 돌아오는 대답은 "문제와 예제를 보세요" 였다. 매운 맛의 단계가 문제에서 전혀 정의되어 있지 않았기 때문에 나는 본문과 예제를 통해 매운 맛의 단계의 뜻을 때려 맞췄다. 하지만 구현을 해서 제출을 계속 해 봐도 WA가 떴고, 4~5번 쯤 틀리고 나니 내가 잘못 푼 건지, 매운 맛의 단계를 잘못 해석한 건지 모호해지기 시작했다. 출제진의 답변으로 미루어 보아 추가 질문을 한다고 정보를 얻을 수 있을 것 같지 않아 J를 버리고 다른 문제를 보러 갔다.

 

01:17 G AC

J를 열심히 틀리던 와중 sh0705k가 G를 풀었다.

 

01:42 C AC

J를 포기하고 C를 보니 쉬운 문제였다. 바로 구현해서 AC를 받았다.

 

02:03 J AC

내 J 코드를 검토하던 sh0705k가 코드의 문제점을 지적해줬고, 이를 수정하여 맞출 수 있었다.

 

02:10 H AC

yooshnn이 결국 H를 구현해왔다. 제출했고 AC를 받았다.

 

이 때 쯤 스코어보드가 프리징되었고, 프리징 시점 순위는 2등이었다.

 

02:51 K AC

H AC가 뜨고 나서, 내가 K번 문제의 풀이를 yooshnn에게 설명해줬고, yooshnn은 또 다시 K를 구현하러 떠났다. 그 동안 나는 충분히 풀 수 있다고 생각했던 D와 I를 풀고 있었다. 그러다가, yooshnn이 K를 구현해왔고 AC를 받았다.

 

03:21 D AC

Prefix Sum을 이용한다는 문제인 것은 캐치했는데, 생각보다 어려웠다. 그러다가, 잉여 index를 만들면 구현이 굉장히 간단해진다는 것을 깨닫고 구현하여 AC를 받았다.

 

03:22~

시간은 38분 정도가 남아 있었고, 남은 문제는 F, I, L이었다. F와 L은 너무 어려워 보였기 때문에 I를 풀기로 결정했다. I번 풀이의 핵심은 각 정점에 대한 최소 거리를 받아놓고 이를 바탕으로 dp를 돌리는 것이었다. 구현을 끝나기 10분 전에 완료했고, 시간이 없다고 생각해 제출해 가면서 디버깅을 했다. 결국 끝나기 30초 전 제출이 틀리면서 IUPC가 마무리되었다. 대회가 다 끝나고 소스 코드를 다시 보니, 간선 입력에 있었던 max를 min으로 바꾸니 맞았다... 정말 아쉬웠다.

 

 

총평

일단 작년과 비슷한 난이도로 출제될 것이라는 예상이 틀렸다. 그렇지만 우리 팀의 실력을 감안했을 때, 꽤 좋은 성과를 얻은 것 같아서 기분이 좋았다. 다만 아쉬웠던 것은 J번이었다. J번은 이렇게 많이 틀릴 만한 문제도, 틀려서도 안 되는 문제였다. 다음부터는 틀렸을 때 refresh하는 습관을 꼭 들여야겠다고 절실하게 느꼈다... 그 외에는 특별한 구현 실수 같은 것들이 없어서 좋았다. 나랑 yooshnn의 강점이 각각 다른 곳에 있는데, 이번에는 정확히 각자가 잘 하는 분야에 맞게 문제가 배분되었고, sh0705k가 중간에서 자신이 할 일을 잘 해준 것 같아서 좋은 경험을 얻은 것 같다.

 

shake!에 출전할 기회를 얻어서 너무 기쁘고, shake!도 최선을 다해서 임할 생각이다.