한 회사가 껍데기가 매우 단단한 달걀을 개발했다. 이 달걀이 얼마나 단단한지 시험하기 위해 회사측은 100층짜리 건물에서 달걀을 떨어뜨리는 실험을 기획했다. 실험담당자는 아래층부터 계란을 떨어뜨려 정확히 어느층에서 달걀이 깨지기 시작하는지 알아보고자 한다. 물론 담당자는 최소한의 낙하실험만을 계획하고있다. 실험용 달걀이 2개 뿐이고, 깨지지 않은 달걀은 재사용이 가능하다고 할 때 어떻게 계획을 짜야할까?
(모든 계획은 최악의 상황을 가정할 것!)
해답
예를 들어 30층에서는 깨지지 않은 달걀이 60층에서는 깨졌다고 해보자. 자연스럽게 달걀이 처음으로 깨지는 층은 31층 이상 60층 이하라고 생각 할 수 있다. 즉 30층 이하 61층 이상은 고려할 필요가 없다. 다만 60층에서 달걀 하나가 깨졌으므로 남은 하나의 달갈료 31층부터 한 층씩 노가다를 해야 할 것이며, 최악의 경우 59층까지 실험해야 할 것이다.
위 예시를 통해 달걀 낙하 실험을 다음과 같이 짜야 효율적이란 것을 알 수 있다..
1. 첫번째 달걀을 적당한 층간 간격을 두고 덜어뜨려 범위를 좁힌다.
2. 두번재 달걀을 통해 방금 전 찾은 범위 안의 모든 층을 조사한다.
그렇다면 적당한 층간 간격은 어떻게 찾아야 하는가?
최적화한 낙하실험 횟수가 k라고 하자.
그러면 처음 실험하는 층은 k가 된다. 그래야 k층에서 달걀이 깨져도 두번째 달걀로 1층부터 k-1층가지 실험하여 많아도 k번만에 찾을 수 있게 된다.
첫 k층에서의 실험에서 달걀이 살아남으면 두번째 실험층은 k + (k-1)이 된다. 그래야 k+(k-1)층에서 달걀이 깨져도 두번째 달걀로 k+1층부터 k+(k-1)-1층까지 실험하여 많아도 k만에 찾을 수 있게 된다. 즉 첫달갈이 2번(k층, k+(k-1)층), 두번째달걀이 k-2번(k+1 ~ k+(k-1)-1층) 실험이 쓰이게 된다.. 2 + (k-2) = k.
k+(k-1)층에서도 달걀이 살아남으면 세번째 실험층은 k+(k-1)+(k-2)가 된다. 그래야 k+(k-1)+(k-2)층에서 달걀이 깨져도 두번째 달걀로 k+(k-1)+1층부터 k+(k-1)+(k-2)-1층까지 실험하여 많아도 k번만에 찾을 수 있게 된다. 즉 첫달걀이 3번(k, k+(k-1), k+(k-1)+(k-2)층, 두번째 달걀이 k-3번(k+(k-1)+1 ~ k+(k-1)+(k-2)-1층)실험에 쓰이게 된다. 3 + (k-3) = k.
이 논리를 반복하면 첫번째 달걀은 k, k+(k-1), k+(k-1)+(k-2), ... , k+(k-1)+(k-2)+...+2+1층에서 낙하실험을 가지게 되며, 고로 건물의 층수는 k+(k-1)+(k-2)+...+2+1보다 작아야 함을 알 수 있다.
합공식을 쓰면 k(k+1)/2 ≥ 100. 부등식을 만족하는 가장 작은 숫자는 14이다.
결론:
첫번째 달걀을 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.층에 떨어뜨려 범위를 좁힌다.
두번째 달걀을 통해 방금 전 찾은 범위 안의 모든 층을 조사한다.
이렇게 계획한다면 최악의 경우라도 14번 안에 실험을 마칠 수 있다.
Algorithmic Puzzles(Anany Levitin, Maria Levitin, Oxford) 121번 문제에서 가지고 왔습니다.
