Facebook Hacker Cup 2015 Qualification Round

2015년 1월 9일 (금) 페이스북 해커컵이 열렸다.

대회가 열리는지도 모르고 있었는데 사내에 관심있는 사람들은 모여서 같이 하자는 글이 올라와서 알게되었다.

할 일도 딱히 없어서 회의실에 모여 문제를 풀었다. 저녁 8시에 모였는데 이미 대회는 시작되었더군..

내가 풀기 시작했을 때도 60시간 넘게 남아있었으니.. 예선전답게 문제푸는 시간은 넉넉하게 주어졌다.

(여기에 제시된 코드는 대회때 제출한 것은 아니고, 나름 다듬은 후에 input/output으로 검증한 것임을 알려둔다.)

1. Cooking the Books

주어진 숫자에서 한 번만 swap해서 최소/최대 값을 찾는 문제.

아.. 문제를 읽고 섣불리 풀다가 물먹은 문제다. 역시 방심은 금물..

입력 값이 길지않기 때문에 모든 경우의 수를 만들어도 되고, 그렇게 풀었어야 했는데 머리를 쓴다고 하다가 망했다 -_-;

처음 든 생각은 0을 제외한 가장 작은 수를 앞에다 두면 최소값, 가장 큰 수를 두면 최대값이 된다는 거였다.

그런데 "9990999" 같은 입력을 보는 순간 실수했다는 것을 깨달았다.

한 자리씩 swap 하면서 최소/최대 값을 찾으면 된다.

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/QR/cooking_the_books.cpp

2. New Year's Resolution

음식에 정해진 영양소가 있고 정해진 영양소 값에 맞게 먹어야 하는 문제.

입력 값이 최대 20개 이고, 음식은 일부만 먹을 수 없기 때문에 상태공간이 작다.

에라 모르겠다 전탐색이다. DFS ...

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/QR/new_years_resolution.cpp

3. Laser Maze

일단 문제 이해가 쉽지않았다. -_-;

결국 내가 움직이면 모든 터렛이 90도 시계방향으로 회전, 그리고 레이져 발사!

불행인지 다행인지 레이져는 벽을 뚫을 수 없고, 터렛도 뚫을 수 없다.

문제가 어려웠던 이유는 같은 자리에 몇 번이고 갈 수 있기 때문이었다. 

(즉, 왼쪽으로 갔다가 오른쪽으로 갔다가 다시 왼쪽으로 왔다가 다음에는 왼쪽으로.. )

생각해보니 터렛이 90도씩 도니까 결국 4가지의 상황만 있는거다. 이 상황을 저장해두고 길찾기에 써먹어보자.

* 4가지 상황에 대해 스냅샷을 만들어놓자.

- 터렛을 회전시킨다.

- 레이져를 쏜다 => 어딜 가면 황천길 가는지 체크

이제 가보자

LOOP:

- 큐에서 이동정보를 꺼낸다.

- 위, 아래, 왼쪽, 오른쪽 으로 갈 수 있을까? 체크한다.

- 이동 가능한 곳은 큐에 넣는다.

결국은 BFS로..

코드: https://github.com/xgate/competition/blob/master/hackercup/2015/QR/laser_maze.cpp

대회당시 1번 문제는 틀렸고, 2번 문제는 맞았고, 3번 문제는 사소한 실수로 에러가 나는 바람에 제출도 못했다 -_-;

어쨌든 한 문제라도 맞추면 라운드1으로 갈 수 있기때문에 턱걸이는 했다. 라운드1에서 한 문제라도 풀면 좋겠다.

예선문제

https://www.facebook.com/hackercup/problems.php?round=742632349177460

문제풀이

https://www.facebook.com/notes/1043281905687710