계란 떨어뜨리기 퍼즐: 동적 프로그래밍으로 최소 시도 횟수 구하기

문제 개요

계란 떨어뜨리기(Egg Drop) 퍼즐은 알고리즘 분야에서 가장 유명한 고전 문제 중 하나입니다. n층으로 이루어진 건물과 m개의 계란이 주어졌을 때, 계란을 떨어뜨려도 깨지지 않는 안전한 층을 찾기 위해 필요한 최소 시도 횟수를 구하는 것이 목표입니다.

핵심 조건

특정 층에서 계란이 깨지지 않았다면, 그보다 낮은 층에서도 반드시 깨지지 않습니다.
특정 층에서 계란이 깨졌다면, 그보다 높은 모든 층에서도 반드시 깨집니다.
한 번 깨진 계란은 폐기해야 하며, 깨지지 않은 계란만 다시 사용할 수 있습니다.

입력 및 출력 형식

입력:
계란의 개수와 최대 층 수를 입력합니다. 예를 들어 계란은 4개, 최대 층은 10층입니다.

출력:
Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4

알고리즘 설계

이 문제는 동적 프로그래밍(Dynamic Programming) 기법으로 효율적으로 해결할 수 있습니다. 2차원 테이블 minTrial[i][j]에 'i번째 계란을 사용해 j층까지 확인할 때 필요한 최소 시도 횟수'를 저장하며, 각 층 k에 대해 계란을 떨어뜨렸을 때의 두 가지 경우를 고려합니다.

계란이 깨지는 경우: 남은 계란 i-1개로 아래 k-1층을 확인 → minTrial[i-1][k-1]
계란이 깨지지 않는 경우: 계란 i개로 위의 j-k층을 확인 → minTrial[i][j-k]

최악의 상황에 대비해야 하므로 두 값 중 최댓값을 취하고, 현재 시도 1회를 더합니다. 모든 가능한 k에 대해 이 값을 계산한 뒤 최솟값을 선택하면 정답이 됩니다.

eggTrialCount(eggs, floors)

입력: 계란의 개수, 최대 층 수

출력: 최소 시도 횟수

Begin
    [eggs+1, floors+1] 크기의 행렬 정의
    for i := 1 to eggs, do
        minTrial[i, 1] := 1  // 1층에서는 1번 시도
        minTrial[i, 0] := 0  // 0층에서는 시도 불필요
    done

    for j := 1 to floors, do
        minTrial[1, j] := j  // 계란이 1개면 각 층을 순차적으로 확인
    done

    for i := 2 to eggs, do
        for j := 2 to floors, do
            minTrial[i, j] := ∞
            for k := 1 to j, do
                res := 1 + max(minTrial[i-1, k-1], minTrial[i, j-k])
                if res < minTrial[i, j], then
                    minTrial[i,j] := res
            done
        done
    done

    return minTrial[eggs, floors]
End

C++ 구현 예제

#include<iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a: b;
}

int eggTrialCount(int eggs, int floors) {    // 최악의 경우 최소 시도 횟수
    int minTrial[eggs+1][floors+1];    // i번째 계란, j번째 층에 대한 최소 시도 횟수 저장
    int res;

    for (int i = 1; i <= eggs; i++) {    // 1층에서는 1번 시도, 0층에서는 시도 없음
        minTrial[i][1] = 1;
        minTrial[i][0] = 0;
    }

    for (int j = 1; j <= floors; j++)    // 계란이 1개일 때 각 층마다 필요한 시도 횟수
        minTrial[1][j] = j;

    for (int i = 2; i <= eggs; i++) {    // 계란이 2개 이상일 때
        for (int j = 2; j <= floors; j++) {    // 2층 이상일 때
            minTrial[i][j] = INT_MAX;
            for (int k = 1; k <= j; k++) {
                res = 1 + max(minTrial[i-1][k-1], minTrial[i][j-k]);
                if (res < minTrial[i][j])
                    minTrial[i][j] = res;
            }
        }
    }

    return minTrial[eggs][floors];    // 주어진 계란 수와 층 수에 대한 시도 횟수 반환
}

int main () {
    int egg, maxFloor;
    cout << "Enter number of eggs: "; cin >> egg;
    cout << "Enter max Floor: "; cin >> maxFloor;
    cout << "Minimum number of trials: " << eggTrialCount(egg, maxFloor);
}

실행 결과

Enter number of eggs: 4
Enter max Floor: 10
Minimum number of trials: 4

위 실행 결과에서 계란 4개와 10층 건물이 주어졌을 때, 최악의 경우에도 안전한 층을 찾기 위해 필요한 최소 시도 횟수는 4번임을 확인할 수 있습니다. 이처럼 동적 프로그래밍을 활용하면 단순한 선형 탐색보다 훨씬 적은 시도 횟수로 문제를 해결할 수 있습니다.