Egg Drop Puzzle

Egg Drop Puzzle

http://datagenetics.com/blog/july22012/index.html

달걀이 2개 있을 때 100층 높이의 탑의 달걀이 떨어지는 어느 장소를 달걀을 최소 횟수로 떨어뜨리며 찾는 문제이다.

달걀이 1개 밖에 없다고 생각해보자

1층 부터 100층까지 모든 층에서 달걀을 던져 볼 수 밖에 없다.

달걀이 무한개라고 생각해보자

2진 탐색으로 했을 때 최소 횟수로 알 수 있다.
log2 100 = 6.644 .. 정도가 된다. 이 횟수보다 최소로 알아 낼 수는 없다.

돌아와서 달걀이 2개 있다고 생각해보자

10칸씩 전진한다고 생각해보자

100층에서 달걀이 깨진다면 10,20, …, 90, 100 에 떨어뜨려보고 10번만에 알 수 있다.

그런데 달걀이 99층에서 깨진다고 해보자

10,20, … , 90, 100 을 떨어뜨려 볼 것이다. 그런데 100층에서 한개의 달걀이 깨졌다

그러면 달걀이 1개 밖에 남지 않기 때문에 1.상황으로 돌아가 91,92,93 … 99 를 떨어뜨려볼 수 밖에 없다. 결국 19번의 drop 이 발생한다.

따라서 10칸씩 전진한다고 했을 때 최소 횟수는 19번이다.

굉장한 발전이지만 더 발전시킬 수 없을까 ?

11칸은?, 12칸은?

12,24,…96 으로 뛰다가 96에서 깨졌다고 해보자

우리는 이미 8번의 drop 기회를 써버렸고 11개의 계단을 체크해야 한다. 따라서 19번의 drop 이 발생한다.

전진하는 칸을 늘릴 수록 빠르게 100층까지 갈 수 있지만 깨졌을 때 커버해야 할 영역 역시 늘어난다.

어떤 N칸 만큼 전진한다고 상상해보자. 안깨졌다면 N-1칸 전진시키자 ( 전진이 1칸 더뎌졌지만 커버해야할 칸이 1칸 줄어들었다)

이렇게 N, N-1, N-2, N-3 … 1 까지 간다고 할 때 이 전진한 칸들의 합이 100층이 되는 N을 구하면 되는 것이다.

N(N+1)/2 = 100 이 되면 N은 13.651, 14칸씩 전진 시킬 때 최소 drop 횟수를 가진다. (14번)

달걀이 3개라고 해보자

전체 k층에서 어떤 i층에서 달걀을 drop 한다고 할 때

깨진다면 -> 달걀2개의 문제로 간다. i-1층, 달걀-1

안깨진다면 -> 층수가 다른 달걀3개 문제로 간다. k-i층, 달걀 그대로

결국 큰 문제를 작은 문제들로써 풀 수 있게 된것이다.