2022 SKKU 프로그래밍 대회 in 소프트의 밤 후기

대회 결과

학과 행사에서 진행하는 프로그래밍 대회에 참가했다.

결과는 7솔브/3등을 기록했다. PS를 시작하고 참가한 대회 중 가장 퍼포먼스와 운이 좋았던 대회다. 이 때 재학생이 아니었기 때문에 상금은 받지 못했다. (내 64만원 ㅠㅠ)

문제 세트는 여기서 확인할 수 있다.

---

A. 안녕 클레오파트라~ (백준 25904) (AC/+3min)

$T_i$ 범위가 작아 단순 구현으로 쉽게 풀린다.

---

B. 장인은 도구를~ (백준 25905) (AC/+8min)

10개 중 9개를 골라 곱할 때 최대값을 구하는 문제이다. 순서와 상관없으므로 가장 작은 하나를 빼고 모조리 곱해준다.

---

C. 수렵의 시간이다! (백준 25906) (AC/+105min)

겁나 어지럽게 풀었다. 4번 틀리고 맞은 이유는 3중 for문변수를 i,j,k로 쓰면서 안에 k를 또 사용했기 때문이다. 방어구를 착용하지 않아도 되므로 모든 레벨이 0인 방어구를 선택지로 추가해 $ O(5^2M^3) $ 브루트포스를 돌렸다. 특수한 알고리즘이 필요하진 않지만 지문이 이해하기 어려워 틀린 사람이 많은 것 같다.

---

D. 양과 늑대 (백준 25907) (AC/+20min)

인터렉티브 문제. N일 동안의 (양의 수)-(늑대의 수) 그래프를 그리면 1일에는 +1, N일에는 음수인 연속함수가 나옴을 이용해 이분탐색을 돌리면 된다. 항상 정답인 날이 있다는 것을 알 수 있다. 고등학교 수학시간에 배웠던 사잇값정리가 떠오르는 문제였다.

---

E. 수열의 합 (백준 25908) (AC/+26min)

거의 보자마자 떠올랐다. $ \Sigma_{i=1}^{N} a_i $를 $O(N)$에 구할 수 있으므로 $ \Sigma_{i=1}^{T} a_i - \Sigma_{i=1}^{S-1} a_i  $ 를 구하는 방법으로 하면 $O(N)$에 구할 수 있다.

+ $O(\sqrt N)$ 풀이도 있다는데 한 번 익혀봐야겠다.

---

F. 수확의 계절이다! (백준 25909) (AC/+157min)

처음에는 이 문제가 한계점이라고 생각했지만, 예제를 그림으로 그리다 풀만하다는 것을 깨닫고 푼 문제. Map을 써서 좌표 별로 도착하는 시간을 저장하고, 다시 일반 배열로 복사해와서 이분탐색을 돌리면 된다. Map에 넣는 코드는 $O(bNlogN) $, 이분탐색 코드는 $O(bNlogK)$이다.

---

G. 게이트웨이 정하기 (백준 25910) (AC/+188min)

이 역시 처음에는 트리 DP에 트라이를 섞은 문제인가.. 해서 모르는게 나왔다고 생각했다. Naive하게 구현하면 $O(N^2)$인데, XOR의 특성을 이용하면 뭔가 한 번만 탐색해서 답을 구할 수 있을 것 같았다. X xor X = 0임을 이용해 출발점 하나를 지정해 BFS나 DFS 1번을 돌리고, xor 성질을 이용해 출발점 하나 당 $ O(logX) $만에 비용을 구할 수 있었다. 총 시간복잡도는 $O(NlogX)$로, 트리DP도, 트라이도 아니여서 풀 수 있었다.

---

H, I, J, K번

전부 어려워보였다. 7문제를 풀고 2시간 정도 남아있었고, H번을 읽었는데 선형시간 풀이도 생각하지 못했고, I번이 그나마 쿼리문제에 이해가 쉬워 시도했다. 누적합에 Mo's를 섞은 것 같아 그 위주로 생각했지만 정해는 머지소트 트리라고 한다..

 

 아쉬움이 없었을 정도로 완벽하게 기량을 보인 대회였다. 다가오는 대회들도 이렇게 풀렸으면 좋겠다.