구글 코드잼 2013 본선 1C 라운드 참가 후기

구글 코드잼

구글 코드잼에 대한 설명은 이전 포스팅을 참고하세요.(구글 코드잼 참가 신청)
지난 4월 13일 ~ 14일에 열린 코드잼 예선에 통과하여 본선 1라운드(1A, 1B, 1C)에 진출할 자격을 얻었습니다.
5월 12일 오후 6시부터 오후 8시 반까지 구글 코드잼 2013 본선 1C 라운드(Google Codejam Online Round 1C)가 열렸습니다.

대회 시작 24시간 전에 구글로부터 코드잼 본선 1C 라운드 시작을 알리는 메일이 도착했습니다.

메일

시간에 맞추어 다음 링크에 접속해서 문제를 풀었습니다.
http://code.google.com/codejam

문제

문제는 A~C로 총 3개가 주어졌습니다.

A. Consonants (8점+20점)
B. Pogo (10점+25점)
C. The Great Wall (9점+28점)

A, B, C 문제 모두 small input과 large input이 각각 채점되었습니다.
절대평가로 통과여부가 결정되는 코드잼 예선(Qualification round)와 달리, 본선의 경우 전세계 참가자 중에서 1000등 이내에 들어야 통과할 수 있습니다.

풀이

python을 사용하여 풀었습니다.

A. Consonants

알파벳 단어와 정수 n이 주어지고, 알파벳 단어로부터 연속된 자음이 n개 이상인 substring의 개수를 구하는 문제입니다.
주어진 단어에서 자음을 1, 모음(a, e, i, o, u)을 0으로 치환하고, 연속적인 1이 n개 이상 등장하는지 여부를 알아보는 방식으로 풀었습니다.
파이썬의 리스트를 사용하여 풀었는데, small input의 경우에는 쉽게 답이 얻어졌지만, large input에서는 단어의 글자수가 100만개 이상으로 길어지는 경우에 시간이 오래 걸렸습니다.
결국 시간이 초과되어 large input으로부터 답을 구하지는 못했습니다.

B. Pogo

(0, 0)으로부터 시작해서 1칸, 2칸, 3칸, …씩 차례대로 상하좌우로 이동해서 주어진 좌표에 도달하는 경로를 구하는 문제입니다.
목표 좌표로부터 최소이동횟수를 구한 뒤, 거꾸로 출발해서 (0, 0)까지 도달하는 경로를 찾았습니다.
상하좌우 중 어느 방향으로 이동할지는 현재 좌표와 (0, 0)을 비교해서 결정했습니다.
small, large input 모두 금세 답을 구했습니다.

C. The Great Wall

만리장성을 일정한 날짜 간격으로, 일정하게 이동하면서, 일정하게 변하는 강도로 공격하는 부족들의 침략 성공 횟수를 구하는 문제입니다.
침략이 성공한 뒤에는 해당 구간의 만리장성이 증축된다는 조건이 있습니다.
날짜별로, 부족별로 공격과 성공여부를 확인하는 코드를 작성했지만 시간이 부족해서 풀지 못했습니다.

성적

코드잼 1C

제 최종 성적은 A(8점) + B(10점+25점) + C(0점) = 43점입니다.
등수로는 전세계 672등입니다.
본선 통과의 커트라인인 1000등 이내에 들었기 때문에 다음 라운드에 진출하는 데에 성공했습니다.
이번 본선 1C 라운드에서의 1000등 커트라인은 38점이었습니다.
본선 1A 라운드에서의 36점, 본선 1B 라운드에서의 34점에 비해서는 커트라인 점수가 약간 높습니다.

다음 대회는 Online Round 2이고, 6월 1일 오후 11시에 시작됩니다.
본선 1A, 1B, 1C 라운드를 각각 통과한 총 3000명이 참가할 수 있고, 이 중에서 500등 이내의 성적을 받으면 Online Round 3로 진출합니다.

Round 2

본선 1C 라운드의 전체 성적은 아래 링크를 참조하세요.
Scoreboard – Round 1C 2013 – Google Code Jam

코드잼에 관한 전체 통계(참가자 국가, 사용한 언어 등)는 아래 링크를 참조하세요.
http://www.go-hero.net/jam/

요령

코드잼에서는 input 파일의 형식은 다양하지만 output 파일의 형식은 일정합니다.
따라서 output 파일을 생성하는 코드를 미리 작성해 두고, input을 처리하여 output을 생성하면 시간을 단축할 수 있습니다.

루프를 돌리면서 무작정 트리를 탐색해야만 풀리는 문제는 거의 등장하지 않습니다.
대개는 쉽게 답을 구하는 방법이 정해져 있고, 그 방법을 찾으면 의외로 짧은 코딩으로 답을 구할 수 있습니다.
무작정 트리를 탐색하는 방법으로도 small input의 답을 구할 수는 있지만, large input의 답을 구하기에는 역부족입니다.

코드잼의 문제는 영어로 주어지고, 문제를 정확히 이해해야만 답을 구할 수 있습니다.
문제가 화면 한가득이기 때문에 영어를 모국어로 사용하는 사람이 아닌 경우에는 문제를 이해하는 데에도 시간이 많이 걸립니다.
따라서 구글 번역기(http://translate.google.com/)에 문제를 붙여넣기해서 번역해서 대략적인 내용을 이해한 뒤에 상세한 조건을 파악하기 위해 원문을 참고하는 방법이 권장됩니다.

관련 포스트