백준 오픈 컨테스트, 월간 향유회 2023. 12. · Arena 15 돌아보기
그래 그래 이건 사실이야
그동안 한 번도 참여해보지 못한 솔브드 아레나를 오늘 처음으로 경험했습니다. 그리고 그 결과가 이루 말할 수 없는 수준인 것 같습니다.
아레나에 참여한 후배의 의견인데, 다 풀어야 한다 까지는 아니어도 일단 겉보기에 그렇게 어려운 대회는 아니었던 것 같습니다.
A. 민주주의
지문이 요구하는대로 구현만 한다면 그대로 통과했을 문제입니다. 제 경우 코드를 간단히 짜려다가 어딘가에서 엇나가서 네 번째 시도만에 통과했습니다.
B. 교환 분배법칙
교환법칙 문제도 아니고 분배법칙 문제도 아닙니다. 문제가 요구하는 수식이 성립되는 경우의 수를 구하는 문제였습니다.
문제는 인수의 수(3)와 가능한 범위($-200\,000 \le each \le 200,000$)만큼 단순히 반복문을 돌리면 $O(N^3)$의 시간 복잡도로 시간 초과가 난다는 부분입니다.
\[a + bc = (a + b)(a + c)\] \[a = a ^ 2 + ab + bc \\\\\\\]그래서 제시된 수를 위와 같이 정리하고, $a = 0$인 경우와 $a \ne 0$인 경우를 나눠서 경우의 수를 찾았습니다.
하지만 그렇게 통과한 제출이 없으므로 수식 접근이 어떻게 잘 안된 것 같습니다.
C. 주식 시뮬레이션
순수 구현문제입니다. 지문이 요구하는대로 구현해나가면 될 것 같습니다.
우선 나름 주의한 부분은
- 3, 4번 연산: 주식 가격이 음수로 떨어지면 상장 폐지인가?
- 4, 5번 연산: 그룹 단위 연산 처리 최적화
- 5번 연산: 실수 연산 시 정확도 문제 였습니다.
이렇게 주의하고도 문제 푸는 중에 5번 연산 부분에서 꽤 실수가 있었는데, 다 고치고도 통과하지 못한 걸 보니 어딘가 주의할 부분이 더 있었을 것이 분명합니다.
D. 그래프 변환
제일 처음에 제시되는 그래프는 모든 정점들이 서로 연결된 그래프이고, 이전 그래프의 모든 간선들을 새 그래프에서 정점으로 사용하므로 $_nC_2$를 $k$회만큼 재귀적으로 처리하면 될 것이라고 생각했습니다.
하지만 역시 제대로 통과하지 못했습니다.
왜 망했을까?
물론 1차적인 원인은 분명 실력입니다.
군대에서 알고리즘을 열심히 공부한다거나 하지는 않았으니 실력은 자연스럽게 체감했을 것이 분명합니다. 게다가 최근 공부한 것도 새롭고 어려운 알고리즘만 개념적으로 알아본 것이었고, 백준도 개념 학습용 문제들을 주로 풀었습니다.
하지만 변명거리라고 해야하나 연말이라 일정이 바쁜 것도 있었습니다.
일이 있어서 아침 꼭두새벽부터 서울에 올라갔더니 잠도 부족했고, 커피로 순간 순간을 연명하던 중에 대회 문제를 풀었습니다.
심지어 열차 안에서 문제를 풀었고, 풀다가 그대로 숙면에 들어가 하차역을 놓칠뻔했습니다 ㅎㅎ…;
다음에는 좀 컨디션 관리도 하고 해야겠습니다.