Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 슈퍼 계란 낙하(Super Egg Drop) 문제

K개의 계란과 1층부터 N층까지 있는 건물이 주어져 있다고 가정해 봅시다. 모든 계란은 기능이 완전히 동일하며, 한 번 깨진 계란은 다시 사용할 수 없습니다.

0부터 N 사이의 어딘가에는 특정 층 F가 존재합니다. F보다 높은 층에서 계란을 떨어뜨리면 반드시 깨지고, F층 이하에서 떨어뜨리면 깨지지 않습니다. 매 시도마다 계란 하나를 골라 1층부터 N층 사이의 임의의 층 X에서 떨어뜨릴 수 있습니다.

우리의 목표는 F의 값을 확실하게 알아내는 것입니다. 그렇다면 F의 초기값과 무관하게 항상 F를 정확히 판별하기 위해 필요한 최소 시도 횟수는 얼마일까요?

예를 들어 입력이 K = 2, N = 6이라면 정답은 3이 됩니다.

문제 해결 접근 방식

이 문제는 동적 계획법(DP)과 이분 탐색(Binary Search)을 결합하면 효율적으로 해결할 수 있습니다. 계란을 중간 층 mid에서 떨어뜨렸을 때 두 가지 결과가 발생할 수 있습니다.

  • 계란이 깨진 경우: 사용 가능한 계란은 K-1개가 되고, mid 미만의 층만 확인하면 되므로 solve(K-1, mid-1)이 됩니다.
  • 계란이 깨지지 않은 경우: 계란은 그대로 K개이며, mid 초과의 층만 확인하면 되므로 solve(K, N-mid)가 됩니다.

최악의 상황까지 대비해야 하므로 두 값 중 큰 값을 선택하고, 모든 후보 mid 중에서 그 최댓값이 가장 작아지는 지점을 찾으면 됩니다. 단순 선형 탐색으로는 시간 초과가 발생할 수 있으므로, left와 right 값의 크기 관계를 활용해 이분 탐색으로 mid의 범위를 좁혀 나가는 것이 핵심입니다.

알고리즘 단계

  1. 2차원 메모이제이션 배열 dp를 정의합니다.
  2. 함수 solve()를 정의하고, 인자로 K(계란 개수)와 N(남은 층 수)을 전달받습니다.
  3. N ≤ 1이면 N을 반환합니다.
  4. K == 1이면 N을 반환합니다. 계란이 하나뿐이라면 아래층부터 차례대로 모두 시도해야 하기 때문입니다.
  5. dp[K][N] != -1이면 이미 계산된 값이므로 dp[K][N]을 바로 반환합니다.
  6. ret := N, low := 0, high := N으로 초기화합니다.
  7. low ≤ high인 동안 다음을 반복합니다.
    • mid := low + (high - low) / 2
    • left := 1 + solve(K - 1, mid - 1)
    • right := 1 + solve(K, N - mid)
    • ret := min(ret, max(left, right))
    • left == right이면 반복문을 종료합니다.
    • left < right이면 low := mid + 1, 그렇지 않으면 high := mid - 1로 갱신합니다.
  8. dp[K][N] = ret을 저장한 뒤 반환합니다.

메인(main) 함수에서는 다음 작업을 수행합니다.

  1. (K+1) × (N+1) 크기의 2차원 배열 dp를 생성하고 모든 값을 -1로 초기화합니다.
  2. solve(K, N)의 결과를 반환합니다.

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int>> dp;
   int solve(int K, int N) {
      if (N <= 1)
         return N;
      if (K == 1)
         return N;
      if (dp[K][N] != -1)
         return dp[K][N];
      int ret = N;
      int low = 0;
      int high = N;
      while (low <= high) {
         int mid = low + (high - low) / 2;
         int left = 1 + solve(K - 1, mid - 1);
         int right = 1 + solve(K, N - mid);
         ret = min(ret, max(left, right));
         if (left == right)
         break;
         if (left < right) {
            low = mid + 1;
         } else
            high = mid - 1;
      }
      return dp[K][N] = ret;
   }
   int superEggDrop(int K, int N) {
      dp = vector<vector<int>>(K + 1, vector<int>(N + 1, -1));
      return solve(K, N);
   }
};
main(){
   Solution ob;
   cout << (ob.superEggDrop(2,6));
}

입력

2, 6

출력

3