제1회 한국항공대학교 프로그래밍 경진대회(KAUPC) 후기

오늘 드디어 한국항공대학교에서 제1회 한국항공대학교 프로그래밍 경진대회(KAUPC)가 진행되었습니다!

제가 참가한 팀의 팀명은 김태현의 생일선물이고, 멤버는 백준 아이디로 hello70825, kimtaehyun98, sky 이렇게 3명에서 참가를 했습니다.

팀명은 제가 정했는데, UCPC랑 ICPC랑 백준 다른 대회 팀명을 보니까 재밌거나 특이한 팀명을 하는 것이 좋아 보여서 대회 다음날 kimtaehyun98님의 생일이라 이렇게 정하게 됐네요 ㅋㅋ

 

팀원들의 실력은 다들 잘하시는 분들이라 굳이 시간을 잡아 따로 연습을 할 필요는 없을 것 같아서 각자 문제를 풀다가 대회 시작 이틀 전과 하루 전에만 같이 연습해보고 대회를 진행하였습니다.

 

 

 

 

제 팀은 최종적으로 모든 문제를 풀었고 1등을 하였습니다.

 

풀이

저는 B -> F -> E 순으로 풀었습니다.

=======================================================================

 

B번. 졸업 사진 - 구현

 

파이썬 기준으로 defaultdict(lambda: [0] * 50001)로 선언하여 장소마다 시작 시각부터 종료 시각까지 1씩을 더해주는 과정을 수행하였습니다. 참고로 이 부분은 누적 합으로 좀 더 최적화할 수 있습니다.

그리고 한 사람이 여러 번 제출할 수 있으니 set에 이름을 넣어주고, 중복을 허용하지 않도록 구현하였습니다. 

 

이렇게 하면 연산 횟수가 100 * 50000에 상수를 곱한 수준으로 연산을 할 테니까 시간 내에 충분히 돌아갈 수 있을 것 같아서 제출하였고 통과하였습니다.

 

=======================================================================

 

E번. 방탈출 - BFS

 

1번 조건이 이해가 안되서 시간을 많이 소모한 문제입니다.

사실 원래 sky님이랑 kimtaehyun98님이 바로 풀이를 찾았는데, 제가 문제를 이상하게 이해를 해서 혼자 태블릿을 켜고 열심히 이상한 소리를 하다가 문제점을 발견해서 20분은 낭비한 것 같네요.

모든 정점에서 BFS를 돌려서 최장 길이를 구하고, 값이 큰 것을 출력하면 통과하였습니다. 이러면 시간복잡도가 O(N * N * BFS)라서 충분히 통과할 수 있습니다.

 

=======================================================================

 

F번. 승부조작 - 구현

 

원래 DP 문제라는데 열심히 노가다해서 통과했습니다.

처음엔 이게 의도한 풀이인 줄 알고 신나게 코드를 짰는데, 코드가 100줄을 넘어서 버리니까 뭔가 잘못된 느낌이 들더라구요... 거의 150줄을 짰습니다.

 

처음엔 문제를 읽고 바로 O(N^2) 탐색 + disjoin-set을 사용하여 풀어야 하나 싶었는데, 더 생각해보니 며칠 전에 풀었던 부산의 해적 문제와 여름방학 때 풀었던 다이아몬드 광산 문제가 떠올랐습니다. 두 문제 목표는 이 문제와 같이 빠르게 모든 배열에 값을 구해야 하는 문제입니다. 그래서 disjoint-set 없이 O(N^2)만으로도 풀 수 있어서 제가 맡아서 풀기로 하였습니다.

 

이 문제에서 답은 두 가지 경우로 나뉘는데, 하나는 백돌을 흑돌로 바꾸지 않고도 흑돌만으로 최대 점수를 구하거나, 백돌을 흑돌로 바꾸어서 최대 점수를 구하는 경우입니다.

 

그래서

1. 가로 방향(→)
2. 가로 반대 방향(←)
3. 세로(↓)
4. 세로 반대 방향(↑)
5. 대각선1(↘)
6. 대각선1 반대 방향(↖)
7. 대각선2(↙)
8. 대각선2 반대 방향(↗)

총 8개의 방향으로 연속된 흑돌의 수를 구하면서 흑돌만 사용했을 때의 최대 점수를 구해주고, (정방향) + 1(백돌) + (반대 방향)으로 백돌을 흑돌로 바꿨을 때의 최대 점수를 구하였습니다.

이렇게 탐색하면 O(N^2)으로 배열에 값을 채울 수 있는데, 부산의 해적이 N=700이었는데 통과했으니 이것도 통과하지 않을까 싶어서 제출했는데 다행히 통과됐네요.

 

그리고 중요한 점은 모서리에 백돌이 있을 경우엔 (정방향) + 1 혹은 1 + (반대 방향)이 최댓값을 가질 수도 있어서 이 부분도 확인을 해줘야 합니다.

 

3
2 2 2
2 1 2
2 2 2

 

 

좀 더 꼼꼼히 생각하고 제출했어야 했는데, 자꾸 하나씩 빠뜨려버려서 많이 제출한 문제입니다.

지금 생각해보니까 다이아몬드 광산처럼 Top-Down으로 풀면 쉽게 됐을텐데 사서 고생을 했네요

 

============================================================================

 

저는 제일 큰 문제가 평소에 알고리즘 문제를 풀 때, 브론즈 티어 문제도 여러 번 제출해야 할 때가 있을만큼 잔 실수가 많은 편이라 대회에서도 그럴까 봐 걱정을 많이 했었는데, F번 문제 빼고는 전부 한 번에 통과해서 다행이였습니다.

 

올해 본격적으로 알고리즘 대회를 준비하였는데, 전부 예선 탈락 아니면 겨우겨우 대회 본선 진출들뿐이라서 실력에 비해 욕심이 많아 회의감이 많이 들었지만 이번에 우승을 하게 되니 회의감은 다 사라지고 더 해볼까하는 생각만 드네요 ㅋㅋㅋ

 

이제 남은 대회가 다음 주에 하는 ACM-ICPC Seoul Regional 본선도 있고, 내년 1월에 하는 경인지역 6개대학 프로그래밍 경시대회 본선이 남았는데 여기서도 만족스러운 결과를 받았으면 좋겠습니다. 감사합니다.

 

===========================================================================

 

상장이 나왔는데 팀원은 3명이지만 상장은 1개....???

 

?????????