5.11 달걀 낙하 퍼즐 - DP

DP로 풀기 위해서는 최악의 경우 최소 시행 횟수를 저장하기 위한 2차원 리스트가 필요.
j층에서 i개의 달걀을 사용할 때 필요한 최소 낙하 횟수 = cache [i][j]
1. 0층은 0번, 1층은 1번 떨어뜨려 보면 됨.
2. 달걀이 1개인 경우 층수와 동일
3. 달걀의 개수별로 리스트를 채워 나감.
 3-1. 달걀이 깨진 경우: 달걀은 i-1개, k-1층인 경우의 값
 3-2. 달걀이 깨지지 않은 경우: 달걀은 i개, j-k층인 경우의 값
4. 두 값 중 큰 값에 낙회 1회를 추가하면 k층에서 낙하할 때 필요한 횟수가 됨.

위의 로직을 코드로 옮기면 다음과 같음.

def solve_dp(n, x):
    cache = [[0 for _ in range(n + 1)] for __ in range(x + 1)]
    for i in range(1, x + 1):
        cache[i][1] = 1

    for j in range(1, n + 1):
        cache[1][j] = j

    for i in range(2, x + 1):
        for j in range(2, n + 1):
            cache[i][j] = 987654321

            for k in range(1, j + 1):
                now = 1 + max(cache[i - 1][k - 1], cache[i][j - k])
                if now < cache[i][j]:
                    cache[i][j] = now

    return cache[x][n]
    

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

드디어 이번 책도 끝이 났다.
마지막 즈음에 와서는(5장) 문제만 풀어보는 내용이었는데
아직도 적응이 좀 덜 된 건지 익숙하질 않아서 시간을 많이 쓴 듯하다.
시간 대비 성과도 많이 안 나오고. ㅠㅠ
그래도 어찌어찌 책 한 권 또 마무리~~