팀 xhaism으로 참가한 xhae입니당. 후기에는 문제 풀이에 대한 다소의 스포일링이 있습니다 ㅠㅠ


당일 아침에 학교에서 시험이 있었습니다. 시험보고 매점에서 점심거리사서 후다닥 돌아오니 한 5분쯤 지났더라고요. 부랴부랴 문제뽑고 pc2를 켰습니다.

A번을 보니 어 이건 그 그거... 유명한 문제인 LIS(Longest Increasing Sequence) 구하기네요. N(1<=N<=100000)개의 원소가 들어올 때 LIS의 길이를 출력하는 문제였습니다. LIS를 구하는 유명한 방법으로 O(N^2)의 동적계획법이 있기는 하지만, 이 문제에서는 N이 최대 10만까지 들어오기에 O(N^2)의 프로그램은 TLE가 날 것 같았습니다. 사실 LIS를 구하는 알고리즘중에는 O(NlgN)의 복잡도를 가지는 알고리즘이 몇몇 있습니다. 예전에 그런 복잡도를 가지는 방법이 있다는 말만 듣고 우와 대단해 하면서 그냥 넘어갔었는데-...


검색했습니다 ㄲㄲ 구글신 찬양! 이해하고 나서도 직접 코딩하면서 내가 맞게 짜는건지... 어떤지 고민이 되긴 했지만 일단 예제가 나오길래 제출. YES! 이 문제에서 WA(Wrong Answer)받기 시작했으면 아주 돌돌 말렸을텐데 운이 좋았습니다 ㅠ_ㅠ


오픈북(...)으로 A를 풀고 나서 B를 읽다... 영 모르겠어서 스탠딩을 켜보니 E가 풀리고 있었습니다. 바로 E를 읽어보니 simple polygon이 입력될 때 해당 도형의 넓이를 구하는 문제. 신발끈 공식에 대입해서 바로 풀었습니다. 그리고 스탠딩을 다시 보니 아까 그멤버 그대로 I를 풀고 계시길래... I는 2차원 함수의 최대값을 가지는 x의 값을 구하는 문제였습니다. 근해공식 슥슥 대입해서 해결. 그리고 나서 스탠딩을 보니 이제 정체 상태입니다. 1등하신 용자 wook님께서 B를 푸셨길래 다시 B로 돌아가서 읽어봤는데 해법이 잘 떠오르지 않습니다. 조금 생각해보다 일단 다른 문제도 다 읽자고 이때 전 문제를 다 읽었습니다. 그리고 이때 버린 B는 결국 끝까지 못풀었네욤[...] F는 아직도 문제가 깔끔하게 이해가지 않는 부분이 있고, 대충 보아하니 H가 뭔가 수식으로 유도하면 간지나게 풀릴 것 같습니다. 행렬이 주어지고 행렬식을 구하는 문제였는데, 뭔가 곱셈을 하다보면 딱딱 떨어져 나갈거같은 느낌이라... 행렬을 이래저래 바꿔봤는데 잘 안되네요. 그 후에 G를 잡아봤더니 범위가 10^14승입니다. 저는 왠지 범위큰 문제들만 보면 일단 손이 후덜덜 떨리는게 ㅠㅠ 역시 좀 해보다 모르겠어서 패스.


그 후에 C를 다시 읽었는데, 문제를 조금 다르게 읽었습니다. 문제에서 선거를 한다길래 선거의 당선자는 당연히 한명이 있는 거라고 생각했습니다. 당선자가 반드시 한명으로 고정되면 문제가 그리디로 바뀌게 됩니다(아마도). 그래서 열심히 그리디로 짜보니 예제 하나가 계속 안나와서...  예제 설명을 읽어보니 당선자가 없을수도, 여러명일 수도 있더라고요. 솔직히 이시점에서 울고싶었음 ㅠㅠㅜㅜㅠㅠ 그런데 문제를 다시 이해하고 생각해보니 어 이건 2-SAT 문제네. 근데 나는 2-SAT을 풀 줄 모르잖아. 난 아마..


되더라고요. 구글짱... 대회도중에 어떤 알고리즘으로 해결하는지 다 검색하고[...] 코딩을 시작했습니다. 예제가 나와서 섭밋! WA! 또섭밋! WA! 알고보니 내가 섭밋하고 있던건 위에서 그리디로 짠 소스였을 뿐이고! 난 그리디 소스랑 2-SAT 소스 파일명이 비슷했을 뿐이고!

다시 제대로 된 소스를 제출했더니 또 WA! 조금 의심가는 부분이 있어서 고쳐봤는데 또 WA! 그래 막 읽어보고 처음으로 짜본 알고리즘이 맞을 턱이 엇ㅂ지...하면서도 왜 틀렸는지는 모르겠고 반쯤 포기하는 심정으로 Live archive 온라인 저지에 가서 제출을 해봤습니다. 어 근데 Accepted... 이게 무어 ㅠㅠㅠㅠㅠ 이건 LIBe님이 날 해코지하려는 음모가 틀림없다면서 막 저지 다시 봐달라고 때쓰고 난리가 아녔슴다 :( 직접 프로그램 돌려봐주시더니 마지막 하나가 안나온다고... 프로그램이 죽는다고 하시길래 이거 저거 고쳐보다 3번의 WA를 더 받고 나서야 원인을 찾았습니다. 함수 내부에서 원소 2000개짜리 boolean 배열을 하나 선언했는데 이 배열을 전역변수로 뺀 다음에 제출하니 맞더라고요. 그런데 재귀호출도 아니었고 스택 크기를 넘진 않을텐데 흠... 컴맹이라 왜 내부에서 선언했을때 프로그램이 죽었는지는 잘 모르겠습니다 ㅠㅠ 하여간 왠만큼 큰 변수는 전역변수로 선언하는 편이 안전한 것 같네요. 특히 윈도우 베이스에서 채점하는 서울대회는요...


이렇게 안드로메다를 다녀오니 218분에 YES 하나 추가. 이 전문제가 72분에 해결된걸 보면 한 두시간 반정도를 이문제 저문제보며 헤매고 있었네요 ㄲㄲ 곧 스탠딩은 동결되고 적당히 남은 문제를 추리다 대회 끝나갈때쯤 G를 해결. 그리고 대회가 끝났습니다 ㅠㅠ


개인적으로 뭔가 대회 도중에 공부를 많이 하게 된(...) 대회였네요. 몰랐던 알고리즘도 그렇고 프로그램 죽는 문제도 그렇고 좋은 연습이 되었습니다 :)

이 게시물을...