2023 모비스 예선 후기

2022 모비스는 흥미로운 대회였다. 예선때는 채점이 안 되고, 본선 3번에서는 지문이 이상해서 답이 대충 이거겠지~ 하고 찍는 경우가 좀 있었다. 그리고 작년 모비스 대회는 테스트케이스별 점수 시스템이었다. yes no 문제에 답이 no인 테스트케이스를 절반 가량 넣어서 no를 출력하면 문제의 절반 점수를 받는 경우도 생겼다. 이렇듯이 2022 모비스가 흥미로운 대회였으니 이번 대회 역시 어떤 기행을 보여줄지 궁금했다.

 

이번 모비스 시험은 프로그래머스에서 진행한다. 예선 전날에 프로그래머스 사전 체험을 통해서 테스트 환경을 체험해보았다. 우선 코딩창이 너무 작았다. 한번에 대략 10줄 밖에 못 보는 것 같은데 for문 여러개를 중첩하면 헷갈릴 것 같았다. 대충 문제를 읽고 제출해보니까 정확성 영역이랑 효율성 영역 2개의 영역으로 테스트케이스들이 나뉘어져서 채점되었다. 예선에도 정확성 영역이랑 효율성 영역이 있으면 적당히 긁고 가야지 라는 생각이 들었다. 오랜만에 서브태스크 대회를 치는 것 같아서 신났다. (Functioncup을 어쩌다가 못 쳤다)

 

2022 모비스 대회는 마지막 문제에 항상 network flow 문제가 나왔다. 하지만 나는 고등학생때부터 oi 문제만 풀어오던 사람이기 때문에 플로우 문제를 하나도 안 풀었었다... 그래서 예선 전날에 호다닥 열혈강호 5를 풀고 신촌방위본부 탈출을 풀어서 mcmf와 dinic 코드를 짜봤다. 두 문제를 문제없이 풀고 대회장에 들어갈 수 있을까 조금 걱정됐는데 다 짜고 나니까 마음이 평온해졌다.

 

아래부터는 대회중 있었던 일로, 문제 풀이에 대한 스포일러가 있다.

 

예선 시작 시간인 2시가 되고 문제를 봤는데 4문제에 문제별로 배점이 달랐다. 배점이 오름차순이길래 쉬운문제가 앞에 놓여있겠다고 생각하고 앞에서부터 풀었다. 

1번 문제를 읽는데 지문이 길어서 조금 힘들었다. 열심히 읽어보니 적당한 knapsack dp에 priority_queue를 이용한 simulation 문제였다. 숫자 제한이 작길래 시간 생각 안하고 적당히 구현을 열심히 했다. cp를 한지 오래 되기도 했고 코딩창이 작아서 코딩 정확성이 떨어지는 것 같았다. 제출을 했는데 다행히 모든 테스트케이스를 다 맞았다! 상쾌한 출발이었다.

2번 문제는 모비스 문제인 것 같았다. 에어컨 온도를 조절하는데 모비스의 에어컨 시스템이 머시기저시기 하면서 모비스 광고를 했다. 덕분에 문제 지문이 길어서 조금 고생했다. 다시 읽어보니 전형적인 dp 문제였다. 온도의 범위가 대략 -10도에서 40도까지만 고려해도 될 것이라는 추측을 하고 dp를 짜서 맞기를 빌었다. 이번에도 한 번에 모든 테스트케이스를 다 맞았다! 이때쯤에 40분 가량 썼다.

3번부터는 모비스라는 이름이 사라졌다. 지문이 한결 짧아져서 편안했다. 문제를 읽는데 10^9+7이라는 숫자가 나오길래 여기서부터 어렵나보다 했다. 지문을 읽을 때 k 범위가 한 2000일줄 알고 밑으로 제한 창을 넘겼는데 k 범위가 10^9이었다. O(nmdk) 정도의 dp로 슥삭 밀 생각에 싱글벙글하고 있었는데 생각보다 어렵다는 것을 깨달았다. 다시 생각해봤는데 k 범위가 10^9인 것은 분할정복을 이용한 거듭제곱으로 처리하면 뚝딱이라는 것을 알았다. dp로 (i, j)->(k, l)을 한 주기에 이동하는 방법의 가짓수를 구해서  nm * nm 크기의 행렬에 넣은 다음에 열심히 거듭제곱해줘서 풀었다. 시간을 계산하니까 조금 타이트했다. 그리고 이 문제 풀면서 5중 for문을 사용하면서 내 코딩창이 괄호로 꽉 찼다. 위아래로 코드 내리고 올리면서 구현 시간을 조금 깎아먹었다.

4번에는 플로우가 나올 줄 알았는데 자료구조 문제였다! 플로우 나오면 어떡하지 걱정을 많이 했는데 안 나와서 기분이 좋았다. 잘 밀어서 만점을 받고 조기퇴실하는 상상을 했다. 문제를 읽어보니까 집합을 합치고 같은 집합에 있는지 물어보는 문제였는데 언제 들어왔는지를 관리하고 집합을 분리하고 하는 문제였다. 처음 읽을 때는 small to large로 O((N+Q)logN)에 밀 수 있을 줄 알았는데 집합을 합치고 분리하는 과정에서 시간복잡도가 O(N^2)까지 늘어날 수 있음을 깨달았다. 짜고 긁자는 마음으로 O(N^2)짜리 코드를 짰다. 짜는 과정에서 small to large를 같이 가져가면서 나중에 짤 코드를 줄여야지 했는데 어떤 집합을 어디로 옮기는지가 생각보다 중요해서 small to large를 그대로 사용하지 못한다는 것을 늦게 깨닫고 좀 시간을 사용했다. 어찌저찌해서 제출했는데 테스트케이스 6개 빼고 다 맞았다. 이때부터 문제를 못 풀어도 긁었으니까 본선 진출하지 않을까? 라는 안일한 마인드를 장착하게 되었다. 조금 더 생각해보니까 옮기는 시간도 같고 있는 집합도 같으면 같이 움직인다는 것을 깨닫고 분리하는 과정에서 union find를 얹었더니 테스트케이스 3개 빼고 다 맞았다. 이제 집합을 합치는 과정을 어떻게 관리할까에 대한 생각을 했다. 합치는 과정에서도 유니언 파인드를 하나 더 만들어서 합친 시간을 셋으로 관리하면서 union find로 원소들을 합치고 small to large를 사용한다는 기막힌 아이디어를 구현할 생각에 머리가 아팠다. 그러다 잠깐 생각해보니까 집합을 분리하는 과정에서 나온 아이디어를 그대로 적용해도 된다는 아주 간단한 사실을 깨닫고 만점을 받았다. 예선을 만점으로 통과해서 발표까지 편안하게 놀 수 있어서 좋았다.