경희대학교 2025 봄 프로그래밍 경시대회 (KHSPC 2025) 후기

 

 

(2025-05-17에 치러진 본대회 후기임을 알립니다.)

문제 세트

Open Contest 스코어보드 (2025-05-31 시행)

 

후기를 남겨야겠다는 생각은 계속 했었는데, Open Contest 이후 기간이 시험기간이다보니, 글 작성을 계속 미루게 되었네요,, 기억이 많이 날아간 감이 있지만 몇 자 적어보자면..

 

 

2022년도의 첫 교내대회 이후 3년 만에 다시 교내대회를 치르게 되었습니다. 처음엔 알고리즘의 뭣도 모르던 상태라, BFS/DFS 정도만 안 채로 대회를 치렀어서 수상권과는 거리가 많이 멀었습니다. 이후에 알고리즘 공부도 많이 하고 대회 경험도 많이 쌓았기 때문에 이번 교내대회는 수상을 해보고 싶다는 욕심이 생겼습니다.. ㅎㅎ 경희내 교내 ps 멤버를 고려해보았을 때, 우승은 많이 힘들고, 욕심 좀 내보면 2등 정도까지 가능하지 않을까 생각했는데.. 최종적으로 5등(장려상)을 차지하게 되었네요 ㅠ

 

 

 

[00:06:07] A WA

[00:08:24] A AC

긴장이 됐는지 A번부터 문제가 잘 안 읽혔습니다. 간신히 정신을 차린 다음 문제 요구사항대로 구현했다고 생각하고 제출했는데 WA를 받았습니다. 의아해서 문제를 다시 살펴봤는데, 놓친 조건이 하나 있어서 얼른 구현하고 다시 제출해서 AC를 띄웠습니다. 이 시점까지 A를 맞춘 사람은 전부 1try로 맞췄기 때문에 출발이 불안하다고 느꼈습니다.

 

 

[00:22:47] B WA

[00:23:31] B WA

[00:28:07] B WA

B와 G는 Easy와 Hard로 나누어진 문제로, 각각 $N$과 $M$의 제한이 다릅니다. 제한을 생각하지 않고 문제 스타일만 보았을 때에는 냅색 dp를 돌리고 싶게 생겼습니다. 처음엔 dp 풀이밖에 떠오르지 않다가, B번 위치에 있는 이유가 있을 것이라 생각해서 조건을 다시 한 번 뜯어보았는데, $0 \le N \le 2$라는 조건이 있었습니다. 브루트포스를 의도했다는 것은 바로 알아차렸지만 브루트포스를 돌리는 범위를 쉽게 떠올리지 못했고, 또 음수가 섞여 있었기 때문에 구현에서 실수가 날 것이라 생각해 손에 익숙한 dp 풀이를 짜기로 하였습니다.

 

그게 독이 됐을까요.. dp 탐색 범위를 이리저리 조정하며 제출해보았지만 연달아 WA를 맞았습니다.

 

 

[00:34:10] C AC

출발이 불안한 수준이 아니라 초반부를 거의 망치면서 멘탈이 많이 흔들렸습니다. 계속 B를 붙들고 있으면 남은 대회를 모두 망치게 될 것 같아 일단은 보류하고 C로 넘어갔습니다. C는 문제대로 나이브하게 구현하면 $O(N^3)$ 세제곱 풀이가 나오는데, 살짝 고민해보니그래프의 간선 방향을 바꾸어 $O(N^2)$ 제곱 풀이로 줄일 수 있다는 것을 알게 되었고 1try에 AC를 띄웠습니다. 분위기 반전이 필요했던 시점에서 꼭 필요했던 1try AC.

 

 

[00:52:00] E AC

D번은 풀이가 바로 떠오르지 않아 E번으로 넘겼습니다. "또 냅색 dp인가?" 싶어서 다음 문제로 넘길까 했는데, $500$이라는 애매한 숫자가 눈에 들어와서 풀이를 고민해보니, mod $500$을 이용한 dp를 떠올릴 수 있었습니다. 구현 중간에 dp 식 작성을 좀 절어서 시간이 살짝 끌렸는데, 다행히 E번도 한 번에 맞을 수 있었습니다. 

 

 

[01:04:13] B AC

B번이냐 D번이냐의 기로에 있었는데, 이제는 정말 B를 맞춰야할 때지 않나 하는 생각이 들어서 B를 다시 잡았습니다. dp식이 잘못됐다는 생각은 들지 않아서 dp 탐색 범위를 좀 더 고민해보았는데, 마음 편하게 $1\:000\:000$으로 잡으면 충분하지 않을까 하는 생각이 들었고 그렇게 고쳐서 B를 맞추게 되었습니다.

 

 

[01:13:08] D WA

[01:36:49] D TLE

[01:38:26] D WA

[01:41:01] D AC

스코어보드를 보니 D가 풀려 있길래, 다음 문제로 D번을 잡았습니다. 문제를 처음 읽고, 생각보다 풀이가 간단한 것 같아서 금방 짜고 제출했는데 WA를 받았습니다. 알고 보니 문제를 완전히 잘못 이해해서 풀이를 처음부터 다시 고안해야 했습니다. 몇 분을 고민해도 풀이가 생각나지 않아서 스코어보드를 봤는데, D번이 꽤 풀려있었습니다. 그래서 "잘 고민하면 쉬운 문제" + "문제에서 수열 $A$를 등차수열로 준 이유가 있을 것" 이라는 생각을 토대로, 식 정리를 수차례한 후 AC를 띄울 수 있었습니다. 많이 어렵게 푼 것 같긴 하지만.. 어쨌든 맞았으니까 ㅎㅎ..

 

여기까지의 상황에서 앞으로 건드려볼 만한 문제는 F, G, H, J번으로 추려졌습니다. (사실 J번은 이 글을 쓰는 시점 기준으로 P3이라는 높은 난이도의 문제이지만, $N$과 $M$의 제한이 $50\:000$이라 잘만 하면 풀 수 있지 않을까 하는 생각에..) G번에 대해서 어떻게 B번 풀이를 수정하면 맞을 수 있을까를 고민하다가 방법이 잘 보이지 않아서, F번을 고민해보기로 하였습니다.

 

 

[02:13:57] F AC

종이에 MEX 글자만 계속 끄적이다가 무언가 규칙성이 보이는 것 같아서 식정리를 찬찬히 해보기로 하였습니다. 손으로 풀 때는 나름 간단했는데, 생각한 풀이를 코드로 옮기려니 살짝 난해해졌습니다. 이분탐색(매개 변수 탐색)을 살짝 곁들여서 코드를 완성하였고, 기분 좋게도 한 번에 AC를 받았습니다.

 

이 시점에서 6솔브 3등으로 올라가게 되었고, 대회 종료 10분 전까지 5명이 6솔브인 나름의 명장면이 나오면서, 혹시 한 문제를 더 풀고 1등을 할 수 있을까 하는 기대감이 생겼지만..

 

 

[02:54:46] H WA

[02:56:32] H WA

[02:57:37] H WA

[02:58:49] H WA

[~03:00:00] 대회 종료

J번을 계속 시도해보았으나, 마땅히 좋은 풀이가 떠오르지 않았습니다. 스코어보드를 보고 뒤늦게 H번을 잡고 따라가보려고 했지만, 시간이 부족해서 마음도 급해지는 바람에 결국 그대로 대회를 마무리하게 되었습니다.

 

 

 

장려상이라는 좋은 결과를 얻긴 했지만, 개인적으로는 많이 아쉬운 대회였습니다. 좀 더 페널티 관리를 잘했었더라면, 문제 풀이를 좀 더 빨리 떠올렸었더라면.. 하는 생각이 계속 들기도 하고, 풀이 듣는 시간에는 문제 탓도 많이 했었는데, 집 가는 길에 곰곰이 생각해보니 다른 거 탓할 것 없이 그냥 제 실력이 부족해서 이런 결과가 나오지 않았나 하는 생각이 들었습니다. 많이 아쉽긴 했지만 올해 다른 대회들이 많이 남아 있고, 최종적으로는 ICPC에서 좋은 성과를 내는 것이 목표이기 때문에 앞으로 더 열심히 연습해야될 것 같습니다. 

 

화이팅!