들어가며

센트로이드 컵에 내부 참가자로 참여하게 되었다. 교내 대회 이후로는 처음 참여하는데, Centroid 연합 대회는 2025 Centroid Cup 당시에 BOJ가 있었기 때문에 백준에서 Open Contest로 문제를 풀어본 기억이 있다. 학교 에브리타임에 올라온 공고를 보고 참여하게 되었고, 소학회 내부에서 팀 매칭까지 진행해준 덕에 화요일(8일)에 같은 팀원으로 등록할 분을 알게 되었다.

이전 교내대회에서 사용하던 팀노트가 있는데, 풀페이지가 아니기 때문에 조금 손을 본 팀노트를 사용하여 참여하게 되었다. Overleaf에서 작성한 파일을 제공해드렸고 종합한 pdf 파일을 금요일에 다시 전달받을 수 있었다. 내 개발 환경은 데스크탑도 노트북도 전부 Windows & VSCode/Visual Studio 기반인데 팀원분은 Mac & Xcode다 보니 일단은 구현은 팀원분의 노트북으로 진행하게 되었다.

대회 당일

대회가 이루어지는 위치는 중앙대학교 서울캠퍼스 100주년 기념관(310관)이었는데, 솔직히 말하면 생각보다 거리가 좀 먼 편이었다. 어차피 통학도 멀리 다니는 나로서는 크게 문제는 없었지만. 그렇게 들어가기 전에 중앙대학교 후문 앞쪽에서 간식을 나름 좀 사가게 되었다. PT를 다니고 있어서 최대한 당류를 덜 먹을라고 제로 음료를 사가는 것도 있었지만 카페인 도핑을 위해 몬스터를 사간 것이 이후에 어떻게 작용할지 나는 몰랐다

그렇게 중앙대학교 구경을 좀 하다가 올라가서 팀원분을 기다리다 맞춰서 들어가게 되었고, 자리에서 세팅을 진행했다. 내부에 준비된 멀티탭에 가져온 멀티탭을 연결하고, 팀노트 및 간식들과 노트북 등을 세팅하고. 백준이 운영중이었다면 BOJ를 사용했겠지만 공교롭게도 나는 첫 참여하는 대회부터 백준을 떠나보낸 뒤의 대회였기 때문에, 대회 진행은 DOMJudge를 사용한다고 하였다. 맘스터치 버거 야미 거의 몇 달 만에 먹은 햄버거가 너무 맛있었다 트레이너쌤 미안해요

프로그래밍 대회를 여는 오픈소스 플랫폼인데, 다행히도 이전 대회인 교내대회에서도 사용해봤기 때문에 생각보다 문제없이 할 수 있었던 것 같다. 그렇게 처음 뵙게 된 팀원분과 스몰토크를 진행하면서 기다리다가, 대회 시작 시간이 되어 봉투에 있는 문제지를 열어보게 되었다.

간단 문제 후기

문제는 Open Contest가 개최된 플랫폼인
DOJ의 Centroid Cup Open Contest 사이트에서 확인해볼 수 있다. 여기에는 아주 간단한 문제 후기만 남길 생각이다. 괜히 너무 자세히 남기면 그건 그것대로 스포일러가 될 수도 있기 때문에... 문제는 직접 풀어보자. 재밌는 문제들이 많았다.

A. 진짜 해 구성하기

이 문제는 팀원분이 해결해주시고 B번을 내가 시작 문제로 잡았는데, 단순 구현 문제였다. 문자열 구현 및 단순 출력 문제인데 아마 파이썬으로 풀었다면 곱셈 연산으로 반복이 되니까 날먹이 가능했지 않을까 하는 그런 후문. 어차피 cpp여서 상관없었지만...

B. 승차권 검표

처음 풀었던 문제인데 너무 분위기에 압도되어있던 나머지 너무 어렵게 생각한 것 같은 문제이다. 사실 검표 과정에서 적힌 모든 규칙을 금방 이해할 수 있었다.

그래도 문제를 푸는 데 큰 이상은 없었다고 생각한다.

• 승차권의 수들을 $a_1, a_2, \cdots, a_N$으로 두자.
• 이들을 임의의 $p, kp$ 구조로 반복되게 하자. 가령, 2의 배수 꼴로 $2, 4, 6, \cdots$.
• 그러면 임의의 두 수에 대해 $\text{gcd}(a, b)=2$이고, 둘의 합은 2의 배수이며 임의의 두 수의 차는 당연히 2의 배수이다.
• 모든 수의 합은 $\sum_{k=1}^{N}k = \frac{N(N+1)}{2}$에 2를 곱한 형태가 될 것이므로 정수합도 만족할 수 있다.

근데 이걸 무슨 이유로 저 시그마 합을 $N+1$ 부분을 $N-1$로 잘못 둔 탓에 조금 이상한 계산을 했었지만, 출력은 3의 배수를 쭉 나열하는 방식으로 해결했다. 조금 더 일찍 할 수 있었을 뻔했다. 심지어는 1부터 $N$까지 그냥 나열만 해도 됐을텐데...

C. 별점 테러

팀원분이 해결해주신 문제고, 나도 중간에 확인을 조금 했다. 사실상 부동 소수점 처리가 문제가 되는 부분이었던 것 같다. $X$가 소수점 아래 두 자리까지 나타나는데, $NX$의 값이 정수일 때만 구성이 가능하고 $X$의 값의 정수부를 없애고 실수부만 취해서 $N$을 곱한 만큼과 정수부만 $N$을 취한 부분을 나누어 생각하는 방법이 있었을 것이다.

• 입력이 $8$과 $4.25$이면 $4 \times 8$에서 4점씩 8개를 나열한 상태
• $0.25 \times 8 = 2$니까 2개를 더 1씩 올려준다

같은 로직으로 생각해볼 수도 있었을 것이고, 에디토리얼에서도 적당한 방법을 설명해주긴 했다. 나는 다른 문제를 풀고 있었긴 한데, 팀원분은 아마 double 자료형을 사용해서 생기는 부동 소수점 문제로 조금 오류가 났던 부분이 있었던 것 같다.

N. 회의실 예약 시스템 저격

이전 학기에 들었던 알고리즘 강의에서 봤던 회의실 배정 문제의 아류종 문제였다. 회의실 배정 문제의 최적해는 회의들 $(s_i, f_i)$에 대하여 각각의 $f_i$를 중심으로 하고 같은 경우 $s_i$를 기준으로 정렬하여 앞에서부터 겹치지 않게 선택하는 것이 최적해를 보장함을 증명할 수 있다. 근데 여기서는 최적해가 보장되지 않는 유겸이의 알고리즘으로서 $d=f_i-s_i$가 짧은 것부터 선택한다는 조건을 달고 나와서, 예제로 들어온 입력의 범위가 어떤 경우에 -1을 출력해야 하는지 고민하는 것이 최대 관건이었다.

그 증명의 과정이 조금 애매해서 결국 마지막에 시도해보다가 실패했는데, 사실 가설은 맞았었다. 유겸이의 알고리즘으로 배정되어야 하는 회의의 수가 최적해보다 적은 것은 당연하고, 그것이 최적해 두 개를 하나로 묶는 구조면 된다는 가설이었다.

가령, 어떤 회의가 1 3 4 6이면, 유겸이의 알고리즘에서 3 4를 먼저 선택하게 하면 두 회의를 유겸이의 알고리즘에서 한 개로 퉁쳐야 하기 때문에 $2A = B$의 선택이 가능해진다. 근데 이게 회의 수를 첫째 줄에 출력해야 하는 것이다 보니 내가 계산식을 잘못 입력해서 WA가 난 것 같다. 코드의 방법론 자체는 문제가 없었던 것 같은데, 아쉽다.

M. 슬라이딩 퍼즐

이건 내가 푼 문제이다. $N=4$ 퍼즐의 구성이

윗줄    1 2 3 4 1 2 3 4
아랫줄  - - - - - - - -

인 상태를

윗줄    1 1 2 2 3 3 4 4
아랫줄  - - - - - - - -

로 만드는 것이 목적이다. 최적해를 찾는 것을 목적으로 하는 것이 중요했는데, 특정 구조를 반복시키는 것을 목표로 하면 됐다. $N=4$인 경우에 대해 생각해보자.

• 먼저, 4는 맨 끝에 두 개 붙어야 하므로 두 개의 4 사이에 있는 1 2 3을 전부 내리는 데 3회를 사용한다.

윗줄   1 2 3 4 - - - 4
아랫줄 - - - - 1 2 3 -

• 이때의 1 2 3을 적절한 위치에 최소한으로 이동시킨다. 만들 모양의 목표는 아래와 같이 지그재그로 구성하면 된다.

윗줄   1 2 3 4 - - - 4
아랫줄 - 1 - 2 - 3 - -

• 이렇게 만들면 마지막에 아랫줄에 있는 이들을 위로 올리기만 하면 되는데, 그걸 생각하면 가장 왼쪽의 1은 왼쪽으로 3칸, 2는 왼쪽으로 2칸, 1은 왼쪽으로 1칸 움직이면 되는 내림차 구현이 가능하다.
• 윗줄의 2 3 4 역시 오른쪽으로만 가면 방법은 같다.

윗줄   1 - 2 - 3 - 4 4
아랫줄 - 1 - 2 - 3 - -

• 이 상태에서 마지막으로 아랫줄을 전부 올려주면 구성이 가능하다.

이렇게 했을 때 최적해는 앞과 뒤에 $N-1$회 움직이고, 중간의 두 과정에서 $\sum_{k=1}^{N-1}k = \frac{N(N-1)}{2}$이 된다. 그러면 그 최적해는 $2 \times \frac{N(N-1)}{2} + 2 \times (N-1) = N^2 + N - 2$(회)로 계산이 가능하다.

출력 자체도 for loop를 이중으로 구성하여 위치를 적절히 index가 반영하여 위치 출력만 잘 해주면 되기 때문에 물론 그거에 문제가 있었지만 괜찮은 문제였다. $N$이 작아서 이중 for 문도 큰 문제가 없었다는 점.

N. Tessellation

이진 행렬의 구성을 하는 문제고 이 문제는 팀원분이 풀어주셨는데, 끝나고 에디토리얼을 보기 전에 미리 생각해본 결과와 에디토리얼에서 알려주는 것이 유사했다. 내가 직접 푼 문제는 아니므로 자세한 설명은 패스.

O. 제곱수^제곱수^제곱수

양의 정수 $N$을 $M$개의 양의 정수의 합으로 나타내야 하는데 $A_i$와 $N$과 $M$이 모두 제곱수여야 한다는 점에서 잘 읽어봐야 하는 문제였다.

애초에 입력 $N$이 제곱수가 아니라면 조건을 만족할 수 없다. 그러면 사실상... ㅍㅋㅍㅋ
즐거운 문제이다.

후기

팀명을 뭘로 할까 잘 못 정하는 사람이다보니 팀원분께서 정하신 팀명 상받고싶습니다로 참여했는데, 마지막 스코어보드에서 확인한 순위는 내부 팀 기준 9위였다. 아쉬움도 남지만, 내가 실력이 부족한 것도 있었고 팀원분께서 얘기해주셨듯 팀원이 한 명만 더 있었어도 괜찮지 않았을까 하는 아쉬움도 있었다. 그런데 어떻게든 또 상은 받게 되었는데... 이게 정말 웃긴 일이 아닐 수 없었다.

무려 특별상 이름 '컵'. 대회 종료 시점에 컵, 병, 캔의 개수가 가장 많은 팀이었다. 들어오기 전에 사왔던 몬스터 제로 음료수 4캔, 그리고 각각 두고 있었던 물병 2통씩. ... 총 8개가 놓여 있었기 때문에 받게 되었다.
카페인 중독 야르

운영해주시는 분께서도 상받고싶습니다 닉값은 결국 어떻게든 바라면 이루어진다더니 해낸 것 같다고... ㅋㅋㅋㅋ 뭐라도 해냈다!!!

하여튼간에 교내 대회를 제외하고는 이런 대회는 처음으로 나가봤는데 좋은 경험과 좋은 인맥을 만들 수 있어서 정말 좋은 경험이 되었다. 대학을 졸업하기 전에 이런 대회 경험을 또 만들어볼 수 있었으면 좋겠다 하는 생각이 들었다. 그때는 조금 더 PS가 성장한 상태로 치를 수 있기를 바란다.

새로운 추억과 경험을 만들어주신, 대회 운영의 운영진 분들과 검수 및 문제를 제작해주신 모든 분들, 그리고 함께 팀으로 참여해주신 팀원 선배님과 여러 참여자 분들께도 감사의 말씀을 드린다.

다음 대회는 어디가 될까?