11월 23일에 2018 서강대학교 프로그래밍 대회가 3시간동안 열렸습니다. 매년 서강대학교 학부생을 대상으로 열리는 개인 단위의 ACM-ICPC 스타일 알고리즘 대회입니다. 올해로 14년째입니다. (2016년에 제 12회였으니까 아마 올해가 14번째겠죠 ..? 잘 모르겠지만 그럴거에요)

1~2학년만 참가할 수 있는 Master 디비전과 전학년이 참가할 수 있는 Champion 디비전이 있습니다. 저는 오프라인 대회 경험이 별로 없는 새내기라서 Master 디비전에 참가했습니다. 내년부터 알고리즘 학회장을 하게 되기 때문에 교내 대회를 참가자로서 참여하는 건 이번이 처음이자 마지막일지도 모르겠네요 😄

문제는 디비전마다 6문제, 총 12문제였어요. Baekjoon Online Judge에서 오픈 컨테스트를 풀어볼 수 있어요. Master 디비전에는 오픈 컨테스트의 A, C, D, E, G, I 번 문제가, Champion 디비전에는 B, F, H, J, K, L 번 문제가 출제되었습니다.

여름에 2018 전국 대학생 프로그래밍 대회 동아리 연합 대회(UCPC 2018)에서 풍선 스탭으로 일하면서 참가자 분들 책상에 풍선을 달아드렸는데, 이번엔 제 책상에 풍선이 달리는(?) 입장이었어요. 제가 풍선을 달 때는 참가자 분들이 신경쓰이실까봐 다소 걱정도 했지만 문제를 푸는 입장이 되어 보니 생각보다 신경쓰이진 않았어요!

풍선이 많이 달리면 대회장이 예뻐져요. 이런 문화 좋아요!

대회에서 Kotlin을 못 써서 조금 아쉬웠어요. 제 주력 언어는 Kotlin이고, 제가 BOJ에서 푼 문제 중 90% 넘는 문제는 Kotlin으로 풀었거든요. 하지만 학회에서 스터디 하면서 C++에 어느 정도 익숙해져서 딱히 무리는 없었어요. Kotlin은 icpc 월드 파이널 나갈 일이 있다면 거기서 써서 제트브레인의 관심을 한 몸에 받는 거로 만족하고 싶어요. 근데 뭐 일단 월드 파이널을 나갈 수가 있어야..

아무튼 이런 대회가 처음인 새내기의 잡소리는 치워 두고, 문제 이야기를 해 봐요!

문제 이야기

경고: 이 밑에는 솔루션이 있습니다.

솔루션은 제가 문제를 푼 순서입니다.

C. 어려운 소인수분해 / BOJ #16563

A번 풀이가 의외로 곧바로 생각나지 않아서 C부터 풀었습니다. 에라토스테네스의 체는 자신있었거든요.

2와 500만 사이의 자연수가 들어오기 때문에 먼저 $\sqrt{5000000} \approx 2236$까지의 소수를 에라토스테네스의 체로 전처리해 둡니다. 대회에서는 정확하게 500만의 제곱근을 하는 대신 대략 3000으로 잡았습니다. $\pi (2236)=331$이기 때문에, 대략 350개가 안 되는 소수를 얻을 수 있습니다.

어떤 수 n을 입력받습니다. 이제 소수 p에 대해 n이 p로 안 나눠질 때까지 n을 p로 나누고, 동시에 p를 출력합니다. p를 2부터 점점 늘려가다가 n이 $p^2$보다 작아질 경우엔 더 이상 p로 나눠질 리가 없다고 판단하고 루프를 빠져나옵니다. 2236까지의 모든 소수로 나눠봤는데도 n이 1이 아니면, 남아 있는 n 자체가 소수라는 뜻이기 때문에 이 때는 n을 추가로 출력합니다. 이렇게 하면 소인수분해를 해야 되는 수의 개수가 100만 개이더라도 나눗셈을 시도하는 소수 p의 개수가 얼마 안 되기 때문에 큰 걱정이 없습니다. 대회 시작 9분 후 퍼스트 솔브.

A. 3의 배수 / BOJ #16561

의외로 이 문제는 처음에 문제를 잘못 이해해서 고민을 많이 했어요. 자연수 3개로 분할해야 하는데 그걸 놓쳐서 그냥 자연수를 분할하는 갯수로 이해해버렸어요. 아무튼.

문제를 읽어보면 알겠지만 n이 3의 배수인 건 별 의미가 없죠? 사실 $\frac{n}{3}$을 자연수 3개로 분리하는 것과 같습니다. 근데 순서가 상관이 있다고 하네요. 어떻게 분리해야 될까요?

일단 3을 3개로 분리하는 건 1 + 1 + 1 하나밖에 없죠. 4를 3개로 분리하는 건 2 + 1 + 1을 순서를 적절히 바꿔서 3개가 나오고, 5를 3개로 분리하는 건 3 + 1 + 1과 2 + 2 + 1을 순서를 적절히 바꿔서 6개가 나오고… 그러면 이 문제는 공 $\frac{n}{3}$개를 3개의 서로 다른 상자에 각각 1개 이상씩 나눠 담는 경우의 수를 구하는 문제로 생각할 수도 있겠네요! 이건 중복조합 $$\textstyle\left\langle{3\atop {\frac{n}{3}-3}}\right\rangle\left(=_{3}\mathrm{H}_{\frac{n}{3}-3}\right)$$과 같습니다. 계산해 보면 간단히 $$\frac{(\frac{n}{3}-1)(\frac{n}{3}-2)}{2}$$이고, 이렇게 풀면 AC를 받아요!

물론 저는 고등학교 확률과 통계는 잊어버린 지 오래이기 때문에 3, 4, 5, 6을 분할해 보고 각각 1, 3, 6, 10개가 나오는 걸 보고 ‘이건 뭔가 nCr이겠구나!’ 싶어서 바로 그렇게 짰더니 맞았습니다. 대회 시작 14분 후 정답.

B. 친구비 / BOJ #16562

간단한 그래프 문제였어요. 연결 요소들을 찾고, 그 중 최소인 값들만 다 더해주면 됩니다. 연결 요소들은 BFS로 찾든 DFS로 찾든 별 상관은 없고, 모든 노드를 한 번씩만 방문하기 때문에 $O(N)$으로 뚝딱 풀려요. 이 합이 K보다 클 때만 “Oh no”를 출력하면 됩니다. 대회 시작 21분 후 정답.

D. 히오스 프로그래머 / BOJ #16564

팀 목표레벨 T를 0과 $2 \times {10}^{9}$ 사이에서 이진 탐색하는 방식으로 풀었어요. 사실 대회에서는 T의 이론적 최댓값을 신경쓰지 않고 0과 ${10}^{12}$ 사이에서 탐색했어요. 왠진 모르겠지만 범위를 어디까지 잡아야 될지 감이 잘 안 와서..

탐색할 때마다 목표 레벨이 T일 때 올려야 하는 레벨 총합 $\sum \mathrm{max} (0, T-X_i)$를 K와 비교하는 방식이었어요. N이 1백만 이하이고 K가 10억 이하라서 int로 풀면 터지겠죠? 당연히 long long을 썼습니다.

올려야 하는 레벨 총합을 구하는 건 $O(N)$이고 목표 레벨 T를 탐색하는 건 $O\left(\log\left(2\times{10}^{9}\right)\right)$입니다. 따라서 이 문제도 선형 시간 안에 풀립니다. 이진 탐색 범위를 잘못 잡아줘서 한 번 틀리고, 대회 시작 32분 후 퍼스트 솔브.

E. N포커 / BOJ #16565

확률과 통계 문제입니다. 문제지에 숫자를 많이 끄적이게 됐던 거 같아요.

7개를 고를 때를 예로 들어볼게요. 문제의 그림에서 13개의 줄 중 세로줄을 한 개 고르고, 나머지 48장의 카드 중 3장을 고르면 됩니다. 이 때에는 경우의 수가 총 $$\binom{13}{1}\binom{48}{3}$$가지에요.

하지만 11개를 고른다면 어떻게 될까요? 일단 문제의 그림에서 세로줄을 한 개 고르고, 나머지 48장의 카드 중 7개를 고른다고 치면 고른 7장의 카드 중에 또 세로줄을 만드는 경우가 생길 수도 있어요. 이 때엔 세로줄을 두 개 고르고, 나머지 44장의 카드 중에 3장을 고르는 경우를 빼면 됩니다. 경우의 수는 $$\binom{13}{1}\binom{48}{7}-\binom{13}{2}\binom{44}{3}$$가지가 나오겠네요!

15개를 고른다면 어떻게 될까요? 위와 같이 생각한다면 중복을 빼 줄 때 세로줄이 3개 나오는 경우도 빠져버립니다. 따라서 세로줄이 3개 나오는 경우의 수를 다시 더해준다면 $$\binom{13}{1}\binom{48}{11}-\binom{13}{2}\binom{44}{7}+\binom{13}{3}\binom{40}{3}$$가지가 나옵니다.

이쯤 하면 대충 감이 오죠? 일반화할 수 있을 것 같아요. 위의 패턴을 보면 임의의 n에 대해 우리가 구하고자 하는 경우의 수는 $$\sum_{i=1}^{\lfloor n/4 \rfloor} {(-1)}^{i-1} \binom{13}{i}\binom{52 – 4i}{n – 4i}$$가지가 될 것 같고, 실제로도 그래요!

이항 계수를 구하는 게 또 문제인데요, 팩토리얼을 구해 나누는 걸로는 이항 계수를 구할 수가 없어요. long long의 범위는 $2^{63}-1$까지인데, $21! \approx 2^{65.46} $에서 이미 이 범위를 아득히 넘어버리기 때문에 위에 나온 $\binom{48}{7}$을 구하는 건 생각조차 할 수 없을 거에요. long double은 범위는 long long보다 크긴 한데, 엄청 커지면 정확도가 long long보다 못한 것도 있고요. 대신 재귀식 $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$을 쓰면 n ≤ 52, k ≤ 52, k ≤ n에 대해 이항 계수를 다이나믹 프로그래밍으로 전처리해 둘 수 있을 거에요. 숫자가 너무 커질 수도 있간 한데, 어차피 결과는 10,007로 나눈 나머지만 출력하면 되니까 모듈로 연산의 성질을 이용해 전처리할 때 모든 이항 계수는 10,007로 나눈 나머지를 저장하면 돼요.

이렇게 전처리해 둔 이항 계수를 이용하면 n이 얼마가 들어오더라도 최대 13개의 항만 더해서 $O(\lfloor n/4 \rfloor)$에 해결 가능합니다. 식을 잘못 짜서 맞기 전에 3번 틀리고, 대회 시작 1시간 1분 후 퍼스트 솔브.

F. 카드 게임 / BOJ #16566

나중에 알았는데, 이 문제는 원래 Champion 디비전의 F번으로 계획되었다고 합니다. 하지만 이 문제가 더 쉽다고 생각해서 Champion의 F랑 Master의 F를 바꿨다는 것 같습니다. (어쩐지 카드 문제만 연속으로 두 개가 나오더라고요)

여하튼, 처음엔 ‘아 이거 바이너리 서치 트리인가..?’ 하고 한 10분 동안 바이너리 서치 트리를 구현해 보려고 했는데, 트리 연습을 진짜 너무 안 했기 때문에 (게다가 위에서 언급했듯이 Kotlin 하느라 C++에서 struct 짤 일이 별로 없었기 때문에) 포기하고 ‘뭐 어차피 원래 목표는 5등 안에만 드는 거였으니까’ 하고 던지듯이 풀었어요. 근데 맞았습니다!! 이건 데이터가 좀 약했던 것 같아요.

일단 민수가 가져간 카드들을 정렬합니다. 그리고 M의 카드가 쓰였는지 안 쓰였는지 저장하는 플래그 배열을 하나 만듭니다. 이제 철수가 내는 카드의 값을 x라고 할 때, 민수의 카드에서 lower_bound로 x + 1을 찾아봅니다. 이게 아직 안 쓰였다면 바로 출력합니다. 쓰였다면 안 쓰인 카드가 나올 때까지 index를 하나씩 증가시켜 보고, 찾으면 출력합니다.

사실 이 방법은 최악의 경우 $O\left(K^2\log M\right)$이고 TLE가 나도 이상하지 않은 복잡도에요. 그냥 운이 좋았던 것 같아요! 문제를 제대로 풀었다고 말하긴 힘들 거 같지만 여하튼 대회 시작 1시간 47분 후 퍼스트 솔브.

정해는 index sort를 사용하는 것이라고 합니다. M ≤ N ≤ 4,000,000이라서 가능한 것 같은데, 정해로 다시 풀어봐야겠어요.

---

6문제를 전부 풀어 Master 디비전에서 우승했어요. 참가자로서 아마 처음이자 마지막일 교내대회에서 우승한 것이라 개인적으로도 의미가 큽니다. 참가자, 출제진 모두 수고하셨습니다. 좋은 대회 만들어 주신 운영진 분들께 감사합니다!

코딩하다 중간에 백스페이스가 안 먹어서 고생했지만 (나중에 알고 보니 일부 유학생 분들께서 키보드 언어 설정을 자국 언어로 바꿔 두셔서 그랬다는 것 같습니다) 오랜만의 오프라인 대회 너무 재밌었어요. 내년부터는 출제진이 될 것 같은데, 저도 노력해서 모두 재밌게 즐길 수 있을 만한 대회를 만들어보겠습니다 😊

수고하셨어요! 🎈