2022 LG CNS Code Monster 예선 후기

11월 12일 오전 10시부터 1시까지 3시간동안 4문제로 진행되었다.
오랜만에 아침부터 머리 굴리려니 좀 졸렸던 것 같다. 요즘 PS는 후배 가르치는 용도로만 해서 좀 걱정도 됐지만 다행히 실력이 녹슨건 아닌것 같다.

1번 보고 구현이 좀 귀찮겠다 싶어서 그냥 4번까지 쭉 풀이 생각하고 구현은 나중에 몰아서 했다.
거의 1시간동안 1~4번 문제이해&풀이구상을 했다.
1번 구현이 살짝 꼬여서 30분, 2번이 18분, 3번은 7분정도 걸렸다.
4번은 LCA를 원래 짜던 방식으로는 처리하지 못하는 부분이 있어서 살짝 바꿔서 짜느라 중간에 좀 더 생각했었다. 45분정도 걸려서 12시 40분에 무사히 모든 문제를 제출했다.
제출을 해도 결과를 안알려줘서(히든 데이터라고 하나?) 좀 찜찜하기도 하고 지금 생각하니 3번이 시간초과 날지도 모르겠다는 생각도 든다. 하지만 남은 20분동안 코드를 다시 볼 열정은 없었기 때문에...

1번은 문제 읽을때는 좀 어렵겠다 싶었는데 n이 9밖에 안돼서 O(n! * n^3) 정도로 풀었다.
시간제한은 네 문제 모두 10초여서 여유있게 돌렸다.
next_permutation 돌리면서 사전순으로 체크하는데, 일부분만 사용해도 되므로 앞에서부터 i개를 선택해주는 걸로 했다.
누적합을 구해놓고 j로 돌리면서 어디가 중심이 맞는지 체크해주고, 문제 조건에 따라 answer를 업데이트 해줬다.

2번은 문제 이해가 살짝 어려웠다. 입력에서 -1이 콘센트 꼽힌거라는 걸 헷갈려서 살짝 고생했다.
문제의 조건을 잘 보면 항상 트리가 입력되기 때문에 터미널 노드에서부터 그리디하게 채우면서 올라오면 (전체 - 최대 콘센트 수)가 답이 된다.

3번은 문자열 나오길래 살짝 쫄았는데 사이즈가 작아서 그냥 모든 부분 문자열을 set에 때려박고 n제곱 DP 돌렸다.
근데 set에 있는지 없는지 체크하는게 log 붙는데 그생각은 안하고 그냥 냈다.. 시간초과 나려나

4번은 풀이 생각하는 데 시간이 꽤 걸렸다.
일단 문제를 이해하고 손으로 예제 풀어보면서 관찰? 하나를 했다.
루트가 바뀔 때 부모-자식 관계가 뒤집어지는건 기존 루트와 새로운 루트를 연결하는 가장 짧은 경로위의 애들뿐이라는 점...뭐 자명하다.
여기서 바로 LCA를 떠올릴 수는 있지만 그 경로 위의 애들을 다 관리해주려면 결국 시간복잡도가 O(N^2)이 되어버리기 때문에 시간을 단축시키기 위해 구간으로 처리하는 방향으로 생각했다.
트리의 루트에서 리프로 내려오면서 누적합 구하면서 처리해주면 되겠다~라는 느낌으로 '기존 루트 -> LCA -> 새로운 루트'였던 경로를 'LCA -> 기존 루트'와 'LCA -> 새로운 루트' 이렇게 두 구간으로 나눠줬다.
간선을 몇번 지나는 건지 세는 문제였기 때문에 어디서 더하고 어디서 빼야되는지를 조금 신경써줬다.
코드가 꽤 길었는데 사소한 버그는 있었지만 깔끔하게 잘 짜인 것 같아서 기분이 좋았다.

1~3번은 골드, 4번은 플래쯤 될 것 같다. 본선은 나갈 수 있을지는 모르겠지만 예선이 이정도니 꽤 어려울 것으로 예상된다.