google code jam 2010 풀이

Rotate

rotate 후, gravity 적용하는것은 그냥 하면 되고
row, column 은 돌면서 K개 연속으로 있는것 체크하면 되고
실수할 수 있는 부분은 대각선인데,
/은 ㅣㅡ (아래)순으로 돌고
\은 ㅣㅡ(위) 순으로 돌면 된다.
대각선에서 실수 할 수 있다.

그리고 시작위치와 속도 를 주면 K개 연속을 detect하는 펑션을 만들면 로직을 단순화 할 수 있다.
풀이를 보고 나서 .

1. 실제로 rotate후 gravity적용하는 것은 왼쪽으로 밀어주면 끝이다. 굳이 rotate하고 gravity적요을 할 필요가 없다 --;; --> 생각을 하자. 젤 중요한 것은 시간 시간이다.
2. N의 max가 50이므로 굳이 최적화 해서 할 필요없이 모든 칸을 돌면서 8방향을 체크하면 된다. --; --> N이 작으면, 최적화 하는 시간보다  bruteforce로 무식하게 하는것이 시간을 더 절약할 수도 있다. 중요한 것은 시간!

Number Game

dynamic programming 문제이고 turn개념때문에 좀 헷갈릴 수 있다.
small set은 cache로 어쩌 해결할 수 있으나 large set은 너무 시간이 걸렸다.
1억번의 빈 루프를 도는 것만 수분이 걸리는데, largeset중에 백만 x 백만 짜리 문제가 있다.-- 이거 머임?


오류들
- B는 모든 k에 대해서 이겨야 하지만 A는 한 k에 대해서만 이겨도 됨..
- turn별로 다른 cache를 사용해야 했는데 그것으로 오류.
- large set은 백만까지 가므로 기존 알고리즘으로는 한계가 있었음.