5.11 달걀 낙하 퍼즐 - 재귀

이번 문제는 대망의 마지막 문제.
그래서 그런지 풀 수 있는 여러 가지 방법에 대해 소개한다.

문제 : 달걀을 빌딩에서 떨어 뜨릴 때, 달걀이 깨지기 시작하는 최소의 층수를 구하는 문제다. 
만약 10층에서 떨어져서 깨졌고, 9층에서는 깨지지 않았다면 10층이 답이 된다.
단, 10층에서 떨어졌다면 9층 이하에서는 절대 깨지지 않고 10층 이상에서는 무조건 깨진다.

가장 간단한 풀이법은 '선형 탐색법'이다.
말 그대로 1층부터 올라가면서 처음 깨지는 층을 구하면 된다. 만약 달걀이 1개라면 이 방법이 유일하다.

두 번째 간단한 풀이법은 '이진 탐색법'이다.
최댓값의 반에서 달걀을 떨어뜨려 보고(만약 100층이 최대층이면 50층에서 떨어뜨림) 
안 깨졌다면 (51 + 100)/2인 75층에서 떨어뜨려보는 식으로
답을 찾을 때까지 현재 값과 최댓값을 더한 후 반으로 나눠서 찾는 방법이다.
최악의 경우에는 n/2번 떨어뜨려봐야 답을 찾을 수 있다.

세 번째 방법은 '이진 탐색법'에서 나아간 '고정 간격 낙하 풀이법'이다.
반씩 나눠서 진행을 하는 게 아니라 n개의 구간으로 나눠서 떨어뜨려 보는 방법이다.
예를 들어 100층까지 있다면 5개의 구간으로 나눠서 20층, 40층, 60층, 80층 100층에서 떨어뜨린다.
만약 60층에서 깨졌다면 41층부터 59층까지 올라가면서 떨어뜨려보면 된다.
그러나 이 방법의 특이한 점은 구간 수가 늘어나도 필요한 낙하 수가 줄어드는데 한계가 있다는 점이다.
그래서 100개 기준으로 19회의 낙하 수 미만으로는 줄일 수가 없다.

마지막으로는 '고정 간격 낙하 풀이법'을 개선한 '가변 간격 낙하 풀이법'이다.
간격을 하나씩 줄여가면서 낙하를 시키는 방법으로, 만약 계란이 2개밖에 없는 경우에는
최솟값인 14를 기준으로 간격이 1씩 줄어가면서 층수에 맞게 던져보면 된다.

가변 간격 낙하 풀이법을 가지고 재귀 호출로 풀어보기로 한다.
만약 p층에서 낙하 시,
깨진 경우 : 달걀이 깨지기 시작하는 층은 p보다 아래. 그러므로 x-1 개의 달걀을 사용해 p-1층의 구간을 확인해보면서 달걀을 떨어뜨리는 횟수를 세면 됨.
안 깨진 경우 : 달걀이 깨지기 시작하는 층은 p보다 위. 그러므로 x개의 달걀을 사용해 n-p층의 구간을 확인해보면서 달걀을 떨어뜨리는 횟수를 세면 됨.
마지막으로 위의 두 경우 중 최솟값을 반환하면 됨.

상기의 내용을 코드로 옮기면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(n, x):
    if n == 1 or n == 0 or x == 1:
        return n

    init = 987654321

    for p in range(1, n + 1):
        broken = solve(p - 1, x - 1)
        okay = solve(n - p, x)
        now = max(broken, okay)
        init = min(init, now)

    return init + 1


if __name__ == '__main__':
    n, x = map(int, input().split())
    print(solve(n, x))

재귀 자체를 만드는 건 어렵지 않았으나
개념을 이해하는 게 꽤 어렵.. ㅠㅠ