제 5회 국민대학교 알고리즘대회 후기

국민대학교에서 알고리즘 대회가 있었다.

왠만하면 본선은 붙지 않을까 + 붙으면 서울 구경이나 해야지 하는 생각으로 예선을 신청했는데...

예선

예선은 온라인으로 한시간동안 진행했다. 캠 켜고 핸드폰 켜고 귀찮았다.

 

1번은 어디서 많이 본 문제였다. https://codeup.kr/problem.php?id=3095

걍 뚝딱 풀었다. 4분?

 

2번은 사다리타기를 시뮬레이션 하는 문제였다. 간선이 10만개였나?

간선을 단방향으로 분리해서 생각해보면 어차피 한번씩밖에 안지나간다. 그래서 대충 lower_bound 같은거 때려가면서 $O(lgN)$에 간선 따라가는 풀이를 구상했다.

어... 근데 구현이 어렵더라. 한시간 내내 디버깅하다 결국 제출 한번 못해보고 시간이 끝났다.

 

문제는 둘 다 쉬웠다. 근데 내가 개못했을 뿐... 200점 만점에 100점을 받았다.

대회 끝나고 나서 든 생각은 본선 절대로 못가겠구나 싶었다. 본선 커트가 100점에 걸리면 빨리 풀었으니 갈수도 있겠지 하며 기도메타를 시전했다. 근데, 결과 보니 본선 커트 낮아도 한참 낮더라. 8X점인걸로 알고 있다.

 

본선

본선은 국민대학교 미래관에서 오프라인으로 진행했다. 창원에 사는 나는 무려 비행기를 타고 당일치기로 다녀왔다.

 

1번은 이거 였다. 읽고 그래프 만들고 도달가능성 따지면 될 거 같은데 당장 생각나는건 N번 탐색밖에 없었다. 근데 N이 10,000이길래 제곱은 안되겠구나 싶어서 이상한 풀이들을 막 생각했다. dfs 스패닝 트리에 스몰투라지에 뭐 이상한거 막 생각하다가 시간은 30분가량이 흘렀고, 에라 모르겠다 하고 N번 dfs를 돌리는 풀이를 짰다. 근데 만점 맞더라. 40분 조금 넘었을 때 2번으로 넘어갔다.

 

2번 문제는 일단 지문과 예제가 상당히 더러웠다. 아니 프로그래머스 예제 vector로 좀 안줬으면 좋겠다. 깔끔하게 보여주면 얼마나 좋아.

union-find로 같은 그룹을 묶어주고 물건을 나눌때는 prefix sum으로 더해주면 된다. 풀이는 바로 생각했고 짜기 시작했는데, 문제가 생겼다. 화장실이 너무 급했다 ㅋㅋ. 아무튼 화장실 다녀 와서 편하게 짜고 디버깅 몇번 하다가 만점을 받았다.

 

아마 1시간 15분쯤 퇴실했던 거 같고 먼저 나와있던 사람에 의하면 7번째로 나왔다고 한다. 동상 컷이 6등이던데 동상을 받을 수 있을까?

 

[08.24 수정]

장려상 받았다. 장려상 1등인듯.

80점도 장려 200점도 장려 할많하않...