C언어가 나올때까지 리플래쉬 해서 찍은 이미지!
뛰어난 프로그래머의 등용문 이라고 불려지는 구글 코드잼!
24시간이라는 제한시간에 3문제 밖에 나오지 않아서 처음엔 문제의 난이도가 얼마나 어려운거야 @_@ 라고 생각을 했는데, 이미 3문제를 모두 푼 사람이 수두룩 했다 -_-;
문제는 생각보다 어렵지 않았다, A와 B번 문제는 쉽게 풀 수 있었는데, small을 한번에 가볍게 통과하고 large도 대회가 끝나고 체점이 된것을 확인하니 모두 통과 50점으로 마감할 수 있었지만.. 문제를 풀었다고 해도 이렇게 풀면 왜 정답이 나오는지는 증명하는 방식을 모른다. 학부 알고리즘 시간에도 알고리즘 증명 방법 같은건 배웠던 기억이...-_-; Algospot에 A번 증명하는 글은 올라왔으니 보고 머리를 굴려보도록 하자!
(문제는 정말 쉬웠는데, 영어 해석이 잘 안됐고 [......] 알고리즘은 쉽게 떠올렸으나 코딩이 잘 안됐다 [......] 코딩연습 부족 ㅠㅠ)
C번은 어려웠다, ACM문제 풀때도 저런 복잡한 그림이 나오면 일단 지나가고 봤었는데 large를 두개다 틀리면(기우였지만) 25점을 넘기지 못해 Online Round1에 진출할 수 없기 때문에 풀려고 덤볐는데.
처음엔 적분을 이용해서 풀까? 라고 생각을 하다가 예전에 풀었던 문제가 생각이 나서(난 적분을 이용해서 풀었는데 같이 스터디를 진행했던 Andstudy분들은 중학교 수학지식으로 풀으셨다. 왠지 진기분 -_-;;) 적분 말고 다른 방법을 골똘히 생각해보기 시작! 하지만 결국 gg를 쳤고, gpgstudy에 누군가가 "이 문제는 적분을 이용해야 한다는군요" 라는 글을 보고 그냥 깔끔하게 적분을 이용해서 풀기 시작했다.
라켓의 전체 영역을구하고 파리를 잡을 수 있는 영역을 구해서 나누는 식으로 문제를 접근!
라켓의 중심을 원점으로 생각하고 1사 분면의 영역만 구한다음에 4를 곱해서 계산을 했는데......
테스트 케이스의 1번째와 3번째는 제대로 나오는데 2번째와 4, 5 번째는 제대로 안나오는거다. 뭐가 문제인지 몇시간 동안 고민을 해보고 디버깅을 해봐도 생각했던 적분 방식대로 코드는 제대로 돌아가고, 혹시 적분 테이블에 있던 root( a² - x² )의 부정적분 연산 결과가 잘못되었나 의심이 들어서 [.....] 몇가지 방식으로 검증도 해봤으나 아무런 이상이 없다.
결국 몹쓸 생각(예시로 나와있는 답이 잘못된거야!)을 해버리고 그대로 풀어서 제출 -____-; incorrect를 받고 gg쳐버리고 그냥 잠을 잤다.
일어나서 회사에서 일을 하려고 해도 머리속에서 계속 맴도는 그 문제, 다시 소스코드를 들여다보니 왠걸.. 파리는 살짝 스치기만 해도 돌아가시기 때문에 모든 Hit영역에 파리의 반지름을 적용해서 계산해야 하는데 안쪽 스트링에는 제대로 적용시켰지만 라켓의 테두리엔 그걸 빼먹었던거다. 안쪽 영역을 구했던 S = R-t; 라는 코드를 S = R-t-f; 로 고치고 (딱 2bytes추가) 제출해보니 Correct.
이것만 풀어도 순위가 2000여 등에서 500등 정도까지 쑥 올라가는건데 너무 아쉽다. 본격적인 Online Round가 시작되면 제대로된 알고리즘 문제가 출제되기 시작할테고, 그럼 아직 잘 모르는 난 실력차이가 확실히 나서 저만치 밀릴꺼 같은데 ㅠ_ㅠ..
더도 말고 덜도 말고 구글코리아에 가서 티셔츠라도 받아봤으면 하는 작은 바람..
