887. Super Egg Drop (Math, Binary Search, Dynamic Programming)

링크 - https://leetcode.com/problems/super-egg-drop/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Hard

Intuition

우리는 dp를 통해서 이 문제를 풀 수 있다. 

dp[move][egg]를 egg의 달걀이 주어지고 move만큼 움직일 수 있다고 할 때, 우리가 체크할 수 있는 가장 maximum floor값을 가진다고 생각하자.

그렇다면 공식은 다음과 같다

dp[move][egg] = dp[move-1][egg-1] + dp[move-1][egg] + 1

이 공식은 다음과 같은 뜻을 가진다

- 만약 move를 한번 한다고 할 때,

- 만약 달걀이 깨진다면, 우리는 dp[move-1][egg-1]의 floors를 체크할 수 있다.

- 만약 달걀이 깨지지 않는다면, 우리는 dp[move-1][egg]의 floors를 체크할 수 있다.

따라서 dp[move][egg]는 number of combinations이며 N의 값에 따라 exponentially 증가한다.

Code

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [[0] * (k+1) for i in range(n+1)]

        for move in range(1, n+1):
            for egg in range(1, k+1):
                dp[move][egg] = dp[move-1][egg-1] + dp[move-1][egg] + 1
            if dp[move][k] >= n:
                return move

Complexity

Time Complexity: O(NK) dp를 만들때 O(KlogN) 2중 for문 일때

Space Complexity: O(NK)