2024 전국 대학생 프로그래밍 경진대회 후기

11월 16일에 전국 대학생 프로그래밍 경진대회가 있다길래 참여해보았습니다.

다음주 ICPC 본선 전에 몸도 풀겸 참여해보았습니다.

시험 환경은 비대면으로 시험을 치는 지라, Softeer에서의 HSAT과 같이 웹캠 등을 켜서 진행했습니다.

 

사전 테스트

사전에 테스트를 쳐야하기에, 한 번 쳐보았습니다. 4문제에 6시간 정도 주어지는데 총 40분 정도 걸렸던 것 같습니다.

사전에 풀었던 문제는 다음과 같았습니다.

 

1. UXUI 디자이너

 문제 : https://level.goorm.io/exam/163020/uxui-%EB%94%94%EC%9E%90%EC%9D%B4%EB%84%88/quiz/1

구름LEVEL

이벤트 - 참여 횟수를 저장할 수 있는 array 하나 만들면 되는 문제였습니다.

그러면, 이벤트 중에서 최대 참여 횟수와 동일한 이벤트들만 출력하면 되니 말이죠.

정렬해도 되고, 안 해도 되는 문제입니다. 

시간복잡도 : O(NlogN+M) or O(N+M).

 

2. 이상한 미로

문제 : https://level.goorm.io/exam/163023/%EC%9D%B4%EC%83%81%ED%95%9C-%EB%AF%B8%EB%A1%9C/quiz/1

구름LEVEL

다익스트라 응용 문제입니다.

A[i]의 값 범위가 1~10 이라면, 항상 나머지의 범위는 0~9 사이입니다.

이를 활용해 거리를 저장하는 array를 dist[left_over][node_number] 이런식으로 저장할 수 있습니다.

PQ에는 해당 노드로 들어오기 전의 노드의 정보를 저장하여 다음으로 향할 노드들 중 어떤 노드만 가능한 지를 파악할 수 있게 해야합니다. 

시간복잡도는 O(10*(V+E)logV).

 

3,4 번은 실제 문제가 없어서 대충 유형만 말하자면...

3번 : Hash map/set을 안다면 쉽게 풀 수 있는 문제였습니다.

4번 : 2차원 누적 합 구현 + 이분 탐색을 요구하는 문제였습니다. 총 시간복잡도는 O(N^2logN).

이렇게 모의 테스트도 시간내로 잘 풀었습니다.

 

본 대회 날

다음날은 본 대회가 있는 날이었습니다.

저는 총 3시간인 줄 알았는데... 14~16시 총 2시간에 4문제였더라구요...

그래도 한 번 풀어보긴 했습니다.

 

문제가 아직 안 올라온 것 같아 대강 풀이만 설명하겠습니다.

 

1. 깡 구현 + 수학 문제.

그리 어렵지 않은 구현 문제였습니다.

숫자 나눈 나머지 가지고 노는 문제였는데 높게 쳐줘도 B3?

 

2. 깡 BFS 문제.

BFS 기본 문제로, 2차원 지도에서 특정 점으로부터 다른 점까지의 최단거리 구하는 문제였습니다.

백준에서는 한 실버 2~1 정도 주긴 할 것 같네요.

 

3. 정렬 + 이분탐색 문제.

대강 배열 내에서 두 원소를 골랐을 때 원소 차이가 K 이하인 경우의 수 구하기인데,

N 범위가 너무 커서 O(N^2)를 막아두었습니다.

 

배열을 정렬하면, a[i]과 차이가 K 이하인 a[j] ( j > i )가 가능한 제일 멀리 떨어져 있는 index라면 a[j-1], a[j-2], ..., a[i+1] 도 가능하게 됩니다.

따라서 이분탐색을 활용하면 O(NlogN) 만에 구할 수 있습니다.

 

백준에서는 한 골3~2 정도 될 것 같아요.

 

4. DP + 최적화???

문제 상황 : 숫자 N개 중에서 K개를 골라서 곱셈, K개를 골라 곱셈한 수를 10으로 나눌 수 있는 횟수 만큼 점수가 됨, 최대 점수?

 

일단 이 문제는 결국 곱셈을 했을 때에 10^k = (2^k *  5^k)의 배수가 되는지가 중요하므로,

각 수를 {2 로 나눌 수 있는 횟수 , 5로 나눌 수 있는 횟수} 이렇게 관리하는 건 맞는 것 같습니다.

 

그런데 이후에 어떻게 풀어야 할 지 감이 잘 안 왔습니다.

아직도 이 문제의 정해는 잘 모르겠지만... (N >= 100이라 bitset DP는 아닌 것 같았음.)

해가 될 수 있는 경우의 수를 계속 줄여나갈 수 있었습니다. 

 

dp[t]는 set으로 t개의 element로 만들 수 있는 점수가 제일 높거나 더 높아질 수 있는 해들의 후보를 저장할 겁니다.

i번째 element를 보고 있는 도중에 dp[t]를 갱신한다면, dp[t-1]에서 가능한 후보를 하나씩 꺼내고 거기에 i를 곱한 결과를 dp[t]에 넣을 수 있습니다.

 

dp[t]에서 절대로 해가 될 수 없는 후보들은 다음과 같습니다.

dp[t]에서 {a1, a2}와 {b1, b2} 가 있을 때 a1 > b1, a2 > b2 라면 {b1,b2}는 절대로 해가 될 수 없습니다.

왜냐하면 i(i > 0)값을 {i1, i2}로 표현하고 각각 a와 b에 곱한다고 생각합시다.

그러면 a * i 와 b * i를 각각 10으로 나눌 수 있는 횟수는 min(a1+i1, a2+i2)  > min(b1+i1, b2+i2) 이런 관계를 가지기 때문에 b는 해가 될 수 없습니다.

 

이런 경우들을 지속적으로 확인하여 해의 후보에서 없애주니 맞았습니다.

저도 시간복잡도 증명까진 못해서 좀 아쉬웠습니다.

결과 : 올솔브 / 1~4번 문제 다 푸는 데 1시간 19분

결과

끼얏호우

 

만점자가 저 혼자였기에 대회에서 1등 하였습니다.

막학기에 이런 대회도 1등 하니 기분이 좋네요.

 

대회 문제들은 체감상 마지막 문제 제외하고는 매우 typical 한 문제들만 나왔다고 생각합니다.

이러한 이유는 문제 풀이 속도가 이를 어느정도 증명한다고 생각합니다.

(문제를 보자마자 아이디어와 시간복잡도 계산이 바로 되긴 했어요.)

다만, 4번째 문제는 정해가 뭔지 엄청 궁금합니다.