SUAPC 2021 SUMMER (신촌지역 대학교 프로그래밍 동아리 연합 여름 대회) 후기

생각보다 정말 많이 어려웠던 대회,

신촌지역 대학교 프로그래밍 동아리 연합 여름 대회(SUAPC 2021 Summer) 후기입니다.

플레티넘에서 군림하고 있던 팀원(버스기사) 두 분과 함께 대회를 준비하고 참가하게 되었습니다.

---

대회 준비

---

우선 전략을 짜기에 앞서 서로 자신있는 알고리즘에 대해 이야기를 나누었습니다.

한 분은 DP와 그리디에 집중해주셨고, 다른 한분은 올라운더이셔서(운전대 담당) 나머지 커버를 해주시고

저는 수학에 약해 그리디와 그래프, 구현 위주로 보자고 이야기를 나눴습니다.

 

대회 전에는 연습을 3번 했습니다.

경북대학교 대회 Gricon 2019, 2020 을 풀었는데,

2019는 생각보다 너무 쉬웠고, 2020은 2019보다 어려웠지만 SUAPC 2020 Winter 보다는 쉬웠습니다.

대회 전날에는 지난 SUAPC 난이도에 맞춰 2019 연세대학교 프로그래밍 경진대회 문제를 풀었습니다.

(이 대회 문제는 정말 어려웠는데, 개인전이었다는 말을 듣고 기겁을 했습니다.)

 

앞서 각자 맡을 알고리즘에 대한 이야기는 했지만, 그렇다고 딱딱 나눠서 풀지는 않았습니다.

SUAPC의 경우 난이도 순서가 랜덤이기 때문에 순서대로 끊어풀기보다

운전대 담당 팀원분의 아이디어로, i번째 문제는 i%3 == 0, 1, 2 에서 각자 나머지값 하나씩을 맡아보기로 했습니다.

개인적으로 정말 좋은 아이디어였다고 생각합니다.

 

대회 준비는 전반적으로 문제 보기 -> 알고리즘 유추 -> 잡을 수 있을 것 같으면 잡고 안될 것 같으면 패스

이런식으로 진행되었습니다.

 

대회 준비 때는 전 1문제를 푸는 경우가 많았고, 나머지는 버스기사님들이 많이 풀어주셔서

대체로 7~8솔 정도 나왔던 것 같습니다.

덕분에 정말 연습을 많이 해야겠다고 생각했고, 실제로 준비기간에 평소보다 문제를 많이 풀었던 것 같습니다.

 

SUAPC 단골 문제인 계산기 문제를 대비해 일부러 우선순위 계산기 문제도 골라 풀었고,

플레티넘 구현 문제도 풀어보려고 노력했습니다. (RPG Extreme...ㅠㅠ..)

---

대회를 하면서

---

처음에 문제를 훑으면서 든 생각은 '어 브론즈가 없네?' 하는 생각이었습니다.

(이후 문제 해설에서도 의도된 난이도에 브론즈 문제가 없었습니다ㄷㄷ)

각각의 문제가 간단하지는 않다고 느껴졌고, 그 중에 그나마 할만하다고 보이는 것들부터 잡기 시작했습니다.

 

저는 처음으로 C번을 잡았는데 검은색 흰색으로 구성된 격자 보드에서,

임의 사이즈의 정사각 체스판의 개수를 구하는 문제였습니다.

처음엔 브루트포스 인줄알고 헤매다가 DP까지 고민했는데도 안풀려서 패스하고 나왔습니다.

 

한분은 스코어보드를 보시다가 F번이 먼저 풀린 것을 보고 바로 F를 잡으셔서 해결하셨습니다.

(대회에서 문제 푸는 전략으로 정말 좋은 전략이라고도 생각합니다)

---

저는 다음으로 A번을 잡았습니다.

최소를 구하는 그리디 문제였는데, 알고리즘이 맞는 것 같아도 계속 틀려서 고민하고 있었습니다.

그러던 중 정말 다행히도, '혹시 초기 비교값을 너무 작게 설정했나?' 하는 생각이 들었습니다.

 

이번 SUAPC 대회 이전에 진행했던 캠프 콘테스트에서

비슷한 이유로 틀렸던 문제가 있었기에 떠오른 아이디어였습니다.

 

제가 고민하는동안 다른 팀원분이 대신 이 문제를 봐주고 계셨는데, 혹시나 싶어 떠올린 아이디어를 제시했고,

다행히 그 아이디어로 A번 문제를 풀 수 있었습니다.

 

TMI지만, 캠프 콘테스트에서 비슷하게 틀렸던 그 문제를 출제하신 분이

지금 팀에서 운전대를 잡아주신, A번을 대신 풀어주신 분이었습니다 ㅋㅋ

.

다른 팀에서는 10번넘게 틀리면서 고생하기도 한 문제였는데, 3번만에 빠르게 풀어서 정말 다행이었습니다.

---

그런데 여기서부터 조금 문제가 생기기 시작했습니다.

다른 팀들이 빠르게 문제를 풀고 있는데, 이 이후로 1시간 이상은 계속 막혀서 2솔에 머물러 있었던 것 같습니다.

다른 상위 팀은 모두 A, F, C, D를 풀어서 최소 4솔은 하고 있는 상태였는데,

우리팀은 A, F를 푼 이후 C, D 문제에서 막힌 상태였습니다.

 

조급한 마음도 들었지만, 일단 차분히 문제를 풀어나갔습니다.

저는 이후로 H번을 잡고 있었고,  아이디어를 떠올려 구현하다가 시간초과에 막혀서 앓고 있었습니다.

 

그렇게 시간이 지나고, C번에 대해서 열띈 아이디어 회의가 오가다가

팀원분이 결국 C번을 해결해주시면서 3솔로 올라갔습니다.

들어보니 dp로 풀었다고 하신 것 같았습니다. 역시 DP 장인다운 모습이셨습니다.

 

곧이어 E번을 잡으셨던 분이 E번도 해결해주시면서, 다른 상위 팀과는 다르게 A F C E로 4솔을 하게 되었습니다.

그리고 이후 스코어보드가 프리즈되고, 대회 종료까지 1시간이 남았습니다.

---

프리즈 이후, 1시간 동안은 2가지에 집중했습니다.

 

1. 다른 상위팀이 모두 해결한 D번, 그렇게 어려운 난이도가 아닐 것이다. 도전해보자.

2. H번은 5솔 이상한 상위팀에서 많이 풀었다. 할 만해 보인다. 해보자.

 

저는 계속해서 H번을 잡다가 잠깐 D로 갔지만, 다시 H로 돌아와서 잡았습니다.

D번은 기댓값 문제였는데, 확률 계산량이 굉장히 많아서 DP를 떠올렸지만,

DP마저도 DP테이블을 꽉꽉채웠다간 메모리초과가 우려되어서, 익숙하지 않은 DP는 넘기는게 맞다고 생각했습니다.

그렇게 프리즈 이후 얼마 안지났을 때, 다른 분이 D번을 해결해주셨습니다. 

 

이후에는 3명이 다같이 달려들어서 H번에 몰두했습니다.

저는 제 풀이 아이디어를 디스코드 방에 올렸고, 각자 다른 알고리즘을 시도해보면서 문제에 다양하게 접근했습니다.

저는 알고리즘이 맞는 것 같은데 계속 시간초과가 나서 굉장히 고민하고 있었습니다

(평소에 문제풀때는 하지도 않던 시간복잡도 계산까지 완벽하게 했는데도 시간초과 였습니다.)

 

혹시 몰라 C++로 옮겨서 제출하니 WA를 받아서 알고리즘이 잘못된 건지 의심하고 있던 찰나,

다른 팀원분이 나누기보다 곱하기 사용을 제안해주셨고,

C++에 익숙하신 팀원분이 제가 옮겨서 제출했던 C++ 코드에 해당 아이디어를 적용하여,

대회 종료 15분전에 드디어 H번을 해결하였습니다.

 

결국 H번 문제를 못 푼 이유는 "파이썬이 느려서" 였습니다....ㅋㅋㅋㅋ

(pypy3조차도 벽을 넘지 못했습니다)

 

그리고 제가 낸 C++ 코드가 틀린 이유는 아마 나누기 연산을 하던 중 오버플로우 문제로 저장 값에 문제가 생겼거나

컴퓨터의 나누기 연산 특유 오차 문제였던 것 같습니다.

 

마지막 15분동안 K번을 시도했지만 실패하면서 대회는 종료되었고,

최종 6솔, 유일 6솔! 그리고 6등으로 마무리하게 되었습니다.

---

대회를 마치며

---

대회 스코어보드 일부. 우승을 못해서(?) 정말로 팀원 모두 각자 사정으로 2학기를 휴학합니다 ㅋㅋ (저는 군휴학..)

우선 대회 난이도는.. 지난 SUAPC 2021 Winter 와 비교했을 때는 비교적 어렵다고 생각했습니다.

(대회 검수진이 플레티넘2를 주고자 하셨던 문제가 Medium 골드 문제로 의도되어 출제되었다고 하니...)

아마 몇몇 문제의 실제 티어는 의도된 티어보다 높게 나올 것 같습니다.

 

이번 대회에서는 0솔브 팀도 정말 많이 나왔습니다.

0솔브 방지 문제가 실버였는데, 0솔, 1솔 팀들의 시도 횟수를 보니 그렇게 쉽지는 않았던 것 같습니다.

(시도횟수 중에 20번대가 많았던 것 같습니다..)

첫 문제를 빠르게 잘 풀어주신 팀원께 다시 한번 감사를..

 

1등부터 4등까지가 8솔브, 5등이 7솔브, 6등이 6솔브

10등까지가 5솔브였는데, 총 문제수가 12문제였습니다.

 

1등에서 두자리수 솔브가 안나온 것도, 6, 7 솔브가 한팀씩 밖에 없는 것도

이 대회의 전체적인 난이도가 쉽지는 않았던 것을 말해주는 것 같습니다.

(지난 대회는 1등 12/13 솔브, 당시 제 팀은 6/13 솔브로 11등을 해서.. 입상을 못했었습니다...)

 

개인적으로 이 대회는 지난 대회와 비교해서 어려운 문제는 여전히 어려웠는데,

쉽게 의도하고 낸 문제가 생각보다 쉽게 풀리지 않았던 점이 체감 난이도가 높았던 이유 같습니다.

마치 수학 모의고사에서 21, 29, 30 난이도는 여전히 어려운데, 18, 19, 20, 28이 전보다는 어렵게 나온 느낌.

심지어 1~8번 문제급 쉬운 난이도(브론즈)가 사라져서 더 어렵게 느껴지는 것도 한몫 한 것 같습니다.

---

개인적으로 아쉬웠던 것은, 제가 C번의 알고리즘을 잘못 유추해서 시도횟수를 낭비하는 바람에

대회 패널티가 늘어난 부분이 좀 많이 아쉬웠습니다.

 

SUAPC는 첫 솔브 이전의 패널티 횟수가 이후 패널티 값에 반영되는 방식이라

첫 솔브를 빠르고 안전하게 하는 것이 중요합니다.

 

이번에는 다행히 6솔이 우리팀밖에 없었지만,

만약 다른 6솔팀이 생겼다면 시간때문에 순위가 밀렸을지도 모르는 일이었습니다.

 

그래서 알고리즘을 판단하고, 가볍게라도 검증한 후에 구현을 하고 제출하는 것이 중요하다고 생각했습니다.

---

또 앞서도 적었지만.. H번..ㅋㅋㅋ

대회에서 "모든 문제에 대해 C++을 제외한 언어로도 충분히 풀 수 있음이 보장되지 않는다" 는 경고가 있는데,

전 그동안 그 경고를 가볍게 무시해왔고, 이번에 드디어 그 경고에 당해봤습니다.

 

앞으로는 시간복잡도 검증까지 끝냈는데도 파이썬으로 시간 내에 안풀리면, C++로 도전해보자

라는 팁을 하나 얻어가게 되었습니다.

역시 이런 문제 때문에라도 C++은 연습을 종종 해놔야겠다는 생각이 드네요.

---

이번 대회에서는 그래도 입상해보자는게 목표였는데, 입상에 성공해서 뿌듯합니다.

전체 6등, 학교에서 2등이면 잘했다는 생각이 드네요 ㅎㅎ

(특히 버스기사 2분께는 아무리 감사의 말을 전해도 모자릅니다.)

 

6등으로 동상, 상금 20만원을 받게 되었고, 아마 책도 받을 것 같습니다.

군대가기 전에 받게 된다면 책은 열심히 읽고 가야겠네요.

 

이 팀으로 또 하게 될지 어떨지 모르겠지만..

대회를 준비하는 동안은 제 스스로가 크게 도움이 안된다는 생각이 들어서 자신감이 많이 떨어졌었습니다.

그래서 군대에 있는 동안에도 백준은 열심히 해야겠다고 생각했습니다.

군대에 있는 동안은 못해도 티어는 플레3, 클래스는 6까지 높여두고 싶네요.

(현재 티어는 플레5, 클래스는 4+)

 

서로 제대하고 더 강해져서 만나면 그때는 꼭 우승해보자는 다짐을 지킬 수 있도록

더 열심히 해야겠다는 생각이 들었던 대회였습니다.