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 디비전에서 우승했어요. 참가자로서 아마 처음이자 마지막일 교내대회에서 우승한 것이라 개인적으로도 의미가 큽니다. 참가자, 출제진 모두 수고하셨습니다. 좋은 대회 만들어 주신 운영진 분들께 감사합니다!
코딩하다 중간에 백스페이스가 안 먹어서 고생했지만 (나중에 알고 보니 일부 유학생 분들께서 키보드 언어 설정을 자국 언어로 바꿔 두셔서 그랬다는 것 같습니다) 오랜만의 오프라인 대회 너무 재밌었어요. 내년부터는 출제진이 될 것 같은데, 저도 노력해서 모두 재밌게 즐길 수 있을 만한 대회를 만들어보겠습니다 😊
수고하셨어요! 🎈