현대모비스 2023 본선 후기

 

 

 

조금 늦은 감이 있지만 그래도 올려놓는게 맞는거같아서 후기 올립니다

 

 

본선 14등으로 아이패드 수상하였습니다!

 

 

 

 

 

1번 문제를 보았고, 잠깐 고민해 보았더니 아주 좋은 그리디 풀이가 떠올랐습니다. 바로 짜서 10.2점을 받았습니다.

 

만점이 아니길래 반례를 잠깐 고민을 했었는데, 다른 사람들도 다 10.2점을 받았길래 테케가 틀렸겠거니 하고 바로 2번으로 넘어갔습니다.

 

(0:10) 1번 +10.2점

 

 

 

 

2번 문제를 잘 기억은 안나는데 뻘짓을 엄청 열심히 했습니다. 문제 상황도 똑바로 이해 못했고, 최단 경로 내부 / 외부 각각에서 처리해줘야 하는 것들이 있는데 둘다 잘못 생각해서 엄청 여러번 고치고 나서야 겨우 돌아가는 코드를 작성했습니다.

 

한참을 디버깅한 뒤 겨우 20점 만점을 받았습니다.

 

(1:30) 2번 +20점

 

 

 

 

이제 다음 문제를 볼까 1번 문제를 볼까 잠깐 고민을 했는데, 구사과님조차 1번을 10.2박고 2, 3번을 풀러 가셨길래 아하 1번은 거들떠도 안봐야겠구나 하고 넘어갔습니다. 이 뒤로 1번문제는 제 머릿속에 지워져서 끝까지 다시 안돌아갔습니다.

 

 

 

3번을 봤습니다. 근데 딱봐도 SCC를 일단 해야될것 처럼 생겼습니다. 문제는 제가 SCC를 짜본지 3년이 돼가서 기억이 하나도 안났습니다. 개념만 알고있는데 뭔가 dfs를 하고 역방향 순으로 뭘 했던거 같은데... 머리가 아파왔습니다. 4번을 읽으러 갔습니다.

 

 

 

4번은 O(QN^2)은 구현하기 어렵지 않은 문제였습니다. 그 이상을 풀기 위해서는 45도를 돌려줘서 뭔가를 더 해야 할 것 같았는데, 대회중에는 시간 여유가 없었어서 깊게 생각해보지는 않고 아 마지막 문젠데 어렵겠지 하고 빨리 포기했습니다.

 

 

아무튼 O(QN^2)으로 짜서 4.9점을 받았습니다.

 

(2:00) 4번 +4.9점

 

번외로 이문제 4.0점이신분들도 많던데 믿음의 N 5000덕분에 테케 하나를 더 맞췄던 것 같습니다. 그 외에도 ans = N * M - 1로 하나를 더 긁을 수 있었다고 하니 억지로 긁으려고 했다면 5.9점까지는 해볼만 했다고 합니다.

 

 

 

다시 3번으로 돌아왔습니다. SCC를 구현해야 아이패드를 받을수 있다 하고 머리 꽁꽁 싸매면서 생각해봤는데.. 생각보다 잘 안떠올랐습니다.

 

 

그러다가.. 다행히도 N = 500임에 착안해서 플로이드-와셜로 SCC를 짜보자! 라는 생각을 했습니다. O(N^3)짜리 SCC를 짜는 기행(...)을 선보이니 실제로 잘 돌아갔습니다.

 

 

근데 SCC를 구현했는데 딱히 문제를 보면서 아무 생각도 안 떠올랐습니다. 아 망했구나. 하고 에라 모르겠다 식으로 outdegree가 0인 점을 세줬더니 12.6점이 나왔습니다.

 

(2:30) 3번 +12.6점

 

 

 

이제 저는 못풀줄 알았던 SCC도 짰고 12.6점도 긁어서 너무 행복해져서 뒤에는 제대로 집중을 못했습니다.

 

 

후에 복기해보니, 12.6점에서 살짝의 휴리스틱만 섞어도 20점까지 금방 올랐고 조금 잘 다룰 경우 26점까지도 받을 수 있었다고 합니다.

 

 

 

 

 

제가 그래프 영역에는 익숙하지 않은 것도 있고, 기하와 더불어 가장 못하는 영역이기도 하다 보니 부족함이 유독 드러났던 지점이였지 않았나 싶습니다. 더 많이 공부해야겠다는 생각을 했습니다.

 

 

 

 

 

최종적으로 10.2 + 20 + 12.6 + 4.9 = 47.7점으로 14등 마무리했습니다.

 

 

대회 끝나고 나서는 아이패드 못받을까봐 살짝 불안했는데 생각했던 것보단 안정권이여서 다행이였습니다.