건물에서 달걀 떨어뜨리는 문제

100층 높이의 건물이 있다.
계란 두 개가 주어지고.
계란을 떨어뜨렸을 때, 계란이 깨지는 가장 낮은 층을 알고 싶다.
(단, 계란이 깨지는 가장 낮은 층이 k라면, k보다 높은 층에서는 모두 깨짐. 한번 떨어뜨렸을 때 깨지지 않았더라도 내구도가 작아진다거나 하진 않음. 계란이니까 당연히 1층에서도 깨지지 하는 개드립은 금지)
계란 두 개가 모두 깨지고 답을 구하지 못하는 경우가 되어서는 안된다.
정확한 답을 구하면서 계란 떨어뜨리는 횟수의 최댓값이 가장 작아지게 하는 방법은?

여기서 최댓값이란, 최댓값을 n이라고 했을때. 계란이 깨지는 층이 몇층이 되건 n번의 횟수 이내로 깨지는 층을 알 수 있다는 얘기이다.
그 n을 최소화하는 방법을 묻는 문제.

여러분은 어떻게 생각하는지.

내가 제안한 해답

: 1층, 11층, 21층, … 이런 순서로 떨어뜨리다가 처음 깨지는 층으로부터 전 9개 층을 다른 달걀로 시도해본다.

이렇게 하면 최대 횟수가 19번이 나옴. 그런데 친구의 말에 따르면 답은 14번이라고 함.

8 comments

  1. binary search를 쓰면 최대 7번에 가능할 것 같은데요. 처음에 50층에서 떨어트리고, 깨지면 아래로, 안깨지면 위로, 25층만큼 바꿔서 해보고, … 반복하면 7번이면 되지 싶은데요. 

    1. 계란이 2개밖에 없다는 것이 문제입니다. 50층에서 떨어뜨렸는데 깨지고 25층에서 떨어뜨렸는데 깨지면 더이상 떨어뜨릴 계란이 없다는 것이죠.

  2. 이거 2010년 정보 여름학교 입교문제였는데 점화식으로 해결 가능하다고 들었음
    D(n,k)가 k개의 계란으로 n층 어쩌고였던거같은데
    기억이 가물가물

  3. 1층씩 떨어트린다. 최대 100번 해야 한다.
    2층씩 떨어트린다. 최대 51번 해야 한다.
    3층씩 떨어트린다. 최대 35번 해야 한다.
    4층씩 떨어트린다. 최대 28번 해야 한다.
    5층씩 떨어트린다. 최대 24번 해야 한다.
    6층씩 떨어트린다. 최대 21번 해야 한다.
    7층씩 떨어트린다. 최대 20번 해야 한다.
    8층씩 떨어트린다. 최대 20번 해야 한다.
    9층씩 떨어트린다. 최대 19번 해야 한다.
    10층씩 떨어트린다. 최대 19번 해야 한다.
    11층씩 떨어트린다. 최대 20번 해야 한다.
    12층씩 떨어트린다. 최대 20번 해야 한다.

    등간격으로 떨어트려서는 14회는 불가능해 보이는데요…

  4. 14회라는 말에 힌트를 얻어서 다시 생각해 보니, 첫회에 14층에서, 두번째에 13층에서, 세번째에 12층에서 … 이런 식으로 떨어트리면 되는군요. 즉, n번째에 15-n층에서 떨어트리면 됩니다.

    그 친구분과 마찬가지로 증명은 생략할게요.

    1. 아, 오해가 생기게 답을 작성했는데, 방금 던진 층보다 그만큼 더 올라간다는 뜻입니다.
      첫회에 14층에서, 두번째는 14+13층에서, 세번째는 14+13+12층에서 … 이런 식이예요.

    2. 네, 저도 따로 알아보니 점점 층 간격을 줄여가면서 하는 방법이 맞더라구요.

댓글을 남겨주세요.