'Google Code Jam'에 해당되는 글 4건
- 2010/05/11 근황. (4)
- 2009/09/13 Google Code Jam 2009 - Round 1
- 2009/09/04 2009 Google Code Jam
- 2008/07/18 Google Code Jam 2008 - Qualification Round (2)
목표했던 라운드1 까지 통과.
B번부터 풀었는데, next_permutation이라는 편한 함수를 이용해서 쉽게 풀 수 있는 문제 였다. 비록 1 wrong try가 있지만 -_-; 단순하게 생각했는데 n자리 숫자이기 때문에 앞에 0이 오면 따로 처리를 해 줘야 했다. ㅠㅠ
그 다음에 A번을 풀었는데, 역시 1 wrong try.. 구문 파싱해서 곱해주기만 하면 되는건데 파싱을 제대로 못해서 결과가 나오지 않았었다. orz..
새벽 1시부터 진행되었던 Round 1B에 참가를 했었는데, (Round 1A는 서울에서 대전에 오는 동안 있어서 참가 못함) C번을 풀려고 하니 벌써 새벽 2시 30분, 대회는 1시간이나 남았지만 졸리고 문제는 어려워 보이고 스코어 보드를 보니 C번을 푼 사람이 100명도 안될꺼 같아 상위 1000등까지 올라가는 대회에 별 지장이 없을꺼 같아서 자버렸는데 아침에 확인해 보니 다행히 통과했다.
Round 2는 Round 1A ~ 1C에서 통과한 3000명이 참가하며 상위 500위 안에 들면 Round 3에 참가 자격이 주어진다. 난 현재의 내 위치를 알기에 Round 3까지 가는건 기대도 하지 않는다. 하하하. 어서 공부하자 -_-;
덧) 우리 나라에선 199명이나 참가를 했는데 반 정도가 Round2 에 올라 간듯. ( http://www.go-hero.net/jam/09/regions/South%20Korea ) 올레~
뛰어난 프로그래머의 등용문 이라고 불려지는 구글 코드잼!
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가 시작되면 제대로된 알고리즘 문제가 출제되기 시작할테고, 그럼 아직 잘 모르는 난 실력차이가 확실히 나서 저만치 밀릴꺼 같은데 ㅠ_ㅠ..
더도 말고 덜도 말고 구글코리아에 가서 티셔츠라도 받아봤으면 하는 작은 바람..
