2012 Gogle code jam Round 1A, I read problems

2012년 code jam round 1A를 읽고 문제 풀이에 대해 생각 까지만 해본 내용들 정리.

http://code.google.com/codejam/contest/1645485/dashboard

Problem A. Password Problem

password를 typing 하다가 말고, 아 틀렸나? 하고 생각이 들 때,

1. 계속 typing을 하는 것이 낫나

2. 지우고 typing을 하는 것이 낫나

3. enter 쳐버리고, 처음부터 다시 typing하는 것이 낫나

기대값을 구하기.

첫 번째 문제라서 그나마 쉬운 편이다. 알고리즘이랄 것이 많이 없고, 구현만 잘하면 된다. 내가 구현하면 2.5시간 쯤 걸릴 것 같다. ^^;;

문제 examples에서 계산 방법을 다 설명으로 써놨더라고.

그런데, 막상 구현을 하다보면 막힐 수도 있다. 경우의 수에 따라서 probability와 keystrokes 값을 각각 구해야 하는데, 이 경우들을 어떻게 정의해야 좋을지 막막할 수 있다.

막연히 다차원 배열로 생각하자면, 이미 입력한 keystrokes 개수에 따라서 차원이 마구 늘어나니 힘들다.

1차원 배열이라고 생각하되, 각 경우의 수에 맞는 값을 하나씩 정의하는 것이 좋겠다. 그렇다면, 각 경우의 수를 어떻게 나열하느냐가 관건인데, 각자 프로그래밍 하기 좋은 방법으로 한 가지 원칙을 설정해서 나열하면 되겠다.

그 중 가장 이해가 잘 가는 방법은 2진수를 그대로 사용하는 것이다. keystrokes가 맞는지 안맞는지를 각 자릿수 bit로 생각하면, 2^n만큼 숫자의 2진수 안에 빼곡히 index를 채워넣을 수 있다.

index를 정의했다고 해서 배열을 사용하면 large input 은 통과할 수가 없다. small input은 통과하게 해놨나보다.

배열을 만들어두지 않고, 각 경우의 값을 dynamic하게 계산하는 것이 좋겠다.

계산하는 것도 모든 index에 대해서 계산하면 large input을 통과할 수가 없다. 시간이 부족해서.

겹치는 것들은 한 번씩만 계산한다.

probability를 계산할 때는 1 bit의 개수가 동일한 것들에 대해서 한 번씩만 계산한다. 이건 어떻게 알아내지? bit를 shift해가면서 세야 하나?

keep typing 하는 경우에 대한 keystrokes 계산은 특정 2^n-1 숫자보다 큰 경우와 그렇지 않은 경우로 나눠서 한 번씩만 계산한다.

m번 backspace 하는 경우 계산은 2^n-1보다 작은 경우와 그렇지 않은 경우로 나눠서 한 번씩만 계산한다.

2진수 계산 연습과 확률 계산 연습을 조금씩 해 놓으면 좋겠다.

한편, google solution에는 엄청 간단한 수식으로 풀 수 있다고 써 있는 것 같다. ^^;;

Problem B. Kingdom Rush

다음 문제도 크게 어렵지는 않을 것 같다. 내가 구현하면 2+2시간은 걸리겠지만 ㅋㅋ.

greedy한 방법으로 풀면 되지 않을까 생각한다. 그렇게 해봐서 안되면 망하는 거고.

무조건 별점 2개짜리 먹기부터 다 채운다. 가능한 것부터 아무거나.

끝나면, 별점 1개짜리 중 먹을 수 있는 것을 먹어본다.

계속 반복해도 도달할 수 없는 것이 없게 되면 Too bad.

나중에 google solution을 봤더니, 다행히 greedy algorithm으로 푸는 게 맞다고 하네. ㅎㅎ.

그렇다면야, 2시간이면 풀 수도 있었겠다.

Problem C. Cruise Control

이 문제 풀이 방법까지는 생각도 못했다. 

나는 문제를 읽는 것도 하나 당 15분 이상씩 걸리고, input, output 처리만 1시간은 걸리는데, 문제를 15분 만에 푸는 괴물들은 도대체 뭐지..

이건 풀기를 시도하더라도 생각해야 할 조건도 종종 생길 것 같다. 차 길이 등.

동시에 같은 거리에 2개 이상의 차가 없는지만 계산하는 방법이 있겠다. 

1초마다 모든 차를 이동해가면서 simulation해봐도 small input은 풀 수 있을지도 모르겠다. 보장 못하지.

simulation하는 경우는 backtracking까지 하는 거면 더 어렵겠다. 차가 모두 앞으로 등속이동을 하니, backtracking이 필요 없을 것 같기도 하다. 딱 한 경우만 나오겠네.

차 3개씩의 모든 set에 대해서 같은 시각에 같은 위치에 있는지를 검사해볼 수도 있겠다. large input까지는 안되겠지?

google solution 을 읽다가 깨달았는데, 차가 추월할 때, 옆으로 순식간에 이동하더라도 그 순간 양측에 차가 없어야 된다는 조건을 구현에 넣기가 쉽지 않았을 것 같다.

아, 해설도 열라 기네. 해설을 읽고 풀으라고 해도 5시간 이상 걸리겠다.

영어 공부부터 해야 할 판.