Joonas' Note

2017 한국 대학생 프로그래밍 경시대회 / ACM-ICPC Daejeon 본선 후기 본문

알고리즘/문제 풀이

2017 한국 대학생 프로그래밍 경시대회 / ACM-ICPC Daejeon 본선 후기

joonas 2017.11.12 00:17


2017 ACM-ICPC 대전 예비소집과 본선을 위해 11월 10일에 팀원들과 함께 대전으로 갔다. (대회는 11일)


PS 공부를 시작한 건 오래되었지만 항상 깊게 공부하지 못했다. 특히 3년 전에 참가했을 때보다 더 못한 실력으로 참가하게 되어서 자괴감이 너무 심했다.

특히 올해는 킹갓갓갓엠페러분들이 너무 많이 참가하셔서 정신 못 차리고 사람들 구경하느라 바빴다.


예비소집 때 기본적인 세팅을 확인하는데, 이번 대회는 특이하게 우분투 16.04 LTS 환경으로 진행됬다. 미리 공지를 확인하고 이미지를 받아서 사용해봤지만 팀원 한 명이 우분투 사용을 힘들어해서 세팅에 신경을 많이 썼다.
예비소집이 끝나고 숙소를 잡으러 택시를 잡으려는데 택시가 진짜 1도 안보였다. 겨우 찾아도 빈차가 아니었고 버스도 건너편에서 지나가는 등 머피의 법칙 겪으면서 1시간동안 문지동을 돌아다녔다. 버스 겨우 타고 숙소까지 가는 데 퇴근시간 겹쳐서 20분 거리를 2시간 넘게 걸려서 도착했다 ㅠㅠ. 그래서 대회날 아침에 1시간 일찍 출발했더니 10분만에 도착해버려서 문지캠퍼스 강제 산책.


대회 날은 아침에 6시 반에 일어나서 편의점에서 간단하게 먹고 출발했다. 전날에 너무 늦게 잠들어서 강당에서 공지사항 듣다가 침흘리면서 잤는 데 사진 찍힐 때 딱 일어났다 ;;


대회가 시작되고 한 명은 IDE를 세팅하고, 나머지는 문제를 나눠서 읽기로 했는 데, 마음이 급한 탓인지 예비소집때처럼 세팅이 잘 되지 않았고 vi 세팅도 못했다.

천천히 문제를 살피다가 팀원이 D번 쉽다고 바로 코딩에 들어갔고 맞췄지만 코딩에서 잔실수를 조금 하느라 생각보다 지체됐었다. 나는 H번이 DP처럼 생겨서 읽고 있었는 데 읽다보니 FFT 같았다. 진짜 망연자실한게 예선 때 FFT를 공부하려다가 미루고 있었는데 나와버린것이다. 유형만 알고 코딩을 모르겠어서 바로 F번을 잡았는데, BOJ 1704 - Z이랑 너무 비슷한 분할정복문제라 손으로 풀고있었다. 나머지 한 명은 I번을 읽고 있었고, 요약해서 내게 알려줬다.

D번을 푼 친구는 C번을 읽었고, LIS를 응용해서 푸는 것 같다고 해서 내가 봤더니 LIS를 적용하기에는 너무 힘든 상황으로 보였고 Greedy가 아니냐고 했다. 친구가 다시 보더니 DP가 떠올랐다고 해서 제출했다가 한번 틀리고 맞았다.

나는 계속 F번을 잡고 있었는데 생각보다 많은 팀이 풀지 못하고있었다. 혹시 문제에 함정이 있는 지 (항상 어려운 문제를 먼저 잡는 기적의 똥손이라) 살펴보는 데, 회전하는 경우의 수만 조심하면 될 것 같았다. 의사 코드로 대충 적어보고 어 될꺼같다! 해서 코딩해서 제출했더니 틀렸다. 어떤 경우인지도 찾았는 데, 이 때부터 두뇌 과부하가 걸렸다. 사망플래그 

팀원이 E번을 읽고 있었는데 시간제한이 0.5초였고 경우의 수도 많아보여서 끙끙대다가 포기. 이때부터는 F번이랑 I번 2개를 동시에 풀고 있었던 거 같다.

I번은 패턴을 뒤에서부터 찾으면 되겠다고 생각하니 KMP의 실패함수가 떠올랐는데 역시 코딩에서 막혀버렸다. 지금 생각하면 F번은 구현 문제에 가까우니까 내가 I번을 잡았어야했는데 둘 다 F번을 잡고 끙끙대다가 결국 못 풀어서 더 아쉬운 게 아닐까싶다.


여담으로 대회 전 2주 정도는 이분매칭을 위주로 공부했는데, 팀원이랑 "이거 이분매칭 아니야?!" 라는 소리만 간절하게 외치고 끝났다.


공식 풀이는 아직 없고, 커뮤니티분이 야매 풀이라고 올려주신걸 확인했는데 접근은 비슷했다. 문제는 기본 원리를 깊게 이해하고 코딩을 잘 했더라면 풀 수 있었을텐데하는 큰 아쉬움! ㅠㅠ

JM북 정주행부터 새로나온 CP 번역본까지 꼼꼼하게 읽고 칼을 갈아야겠다


안그래도 대회 몇주 전부터 가방을 사려다가 시간이 없어서(라고 쓰고 귀찮아서라고 읽는다) 못 샀는데 가방이 생겨서 기분이 매우 좋다! 만족도 200%.

 


내년이면 내게 마지막 ICPC이다. 남은 1년동안 정말 열심히 공부해서 꼭 좋은 성적을 내고 싶다는 욕심이 생겼다.



2 Comments
댓글쓰기 폼