(Week6)[DP] Two Egg Drop (다시보기)

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 1시간 +a

1. 문제 설명

https://leetcode.com/problems/egg-drop-with-2-eggs-and-n-floors/

Egg Drop With 2 Eggs and N Floors - LeetCode

계란의 개수(2개)와 빌딩의 높이(n) 주어질 때, 계란이 깨지는 층이 몇 층인지 알기 위해서는 총 몇 번 던져봐야하는지 구하는 문제. 즉, 계란 2개로 (최악의 경우에도) 가장 적게 던지는 경우는 언제일까? 

2. 접근 방식

아직 완벽하게 이해한 코드는 아니지만, 내가 이해한 부분만 적어두겠다.

초기 아이디어

• 계란 1개를 10층에서 던졌는데 깨졌다면, 10층 아래인 1층~9층을 확인하면 된다. 이때, 남은 계란이 1개이기 때문에 1층에서부터 9층까지 올라오면 된다. (그러다 5층 쯤에서 깨지면 해당 층이 계란이 깨지는 층이다)
• 만약 10층에서 안 깨졌다면? 20층에서 던져보고, 20층에서 깨졌다면 11층~19층까지만 확인하면 된다.

 일단 핵심적인 방법론은 위와 같다고 할 수 있는데, 이를 그냥 적용시킬 수는 없다. 만약, 빌딩의 총 층 수가 100층이고, 10씩 증가시키려고 했다고 가정하자. 그런데 계란이 깨지는 층이 99층이라면 우리는 10층~100층(10번) + 91~99층(9번) 총 19번을 던져야 한다. 하지만 해당 문제에서 100층일 때 최악의 경우에서도 14번이면 확인할 수 있다고 한다. 즉, 10씩 증가시키는 방법이 이해하기에는 직관적이지만, 더 좋은 방법이 있다는 것이다. 이제 이것을 어떻게 14번만에 해결할 수 있는지를 생각해보면 된다.

 

메인 아이디어

 Leetcode를 보면 다음과 같은 예제를 확인할 수 있다.

다음과 같은 예제에서 식이 어떤 식으로 증가하는지 확인하면 다음과 같음을 확인할 수 있다.

$$1, 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100$$

이런 식으로 증가하면, 100일 때(1~99까지 (13번) + 100(1번)) 14번만에 값을 찾을 수 있고, 84이더라도 (1~85 (9번) + 80~84(5번))으로 14번만에 값을 찾을 수 있다. 따라서 웬만한 모든 경우, 최악의 경우에도 14번 만에 계란이 깨지는 층을 알 수 있다. 

 이를 구현하기 위해서, 100부터 1까지 보면 1씩 증가하는 것을 확인할 수 있다. 1부터 100까지 보는 게 아니라 100부터 1까지 어떤 식으로 값을 나눠야하는지 확인해서 이를 코드로 구현한다.  

3. 코드

def twoeggDrop(n):
    dp = [[i for i in range(n+1)],[0 for _ in range(n+1)]] # [[계란이 1개인 경우], [계란이 2개인 경우]]
    jump = 1 # 값을 일정하게 증가시키기 위함
    for start in range(1, n+1):
        while (jump < start) and (max(dp[0][jump-1],dp[1][start-jump])) > max(dp[0][jump], dp[1][start-jump-1]):
            jump += 1
        dp[1][start] = 1 + max(dp[0][jump-1], dp[1][start-jump])
    return dp[1][n]

• DP를 활용하는 이유는 계란이 n층에서 깨졌다면, 남은 계란이 1개인 경우(dp[0])를 생각하면 된다. (완벽하게 이해X) 

4. 코멘트

• 문제를 이해하는데 든 시간에 비해 문제를 푸는 코드는 비교적 간단한다고 볼 수 있다. (생각하기가 힘들다는게 문제)
• 아직 DP를 활용한 while문을 완벽히 이해하지 못했다는 문제도 있다.