계란 던지기 퍼즐을 해결하는 C 프로그램

문제 소개

계란 던지기(Egg Dropping) 퍼즐은 컴퓨터 과학에서 가장 유명한 동적 계획법(Dynamic Programming) 문제 중 하나입니다. n층으로 된 건물과 m개의 계란이 주어졌을 때, 계란을 떨어뜨려도 깨지지 않는 '안전한 층'을 찾기 위해 필요한 최소 드롭 횟수를 구하는 것이 목표입니다.

풀이 전에 알아둬야 할 핵심 조건

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

입력 – 계란의 개수와 건물의 최대 층 수. 예를 들어 계란이 4개이고 최대 층수가 10층이라고 가정해 보겠습니다.

출력 – 최악의 경우에도 안전한 층을 찾기 위해 필요한 최소 시도 횟수, 즉 4회입니다.

알고리즘: eggTrialCount(eggs, floors)

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

출력 – 구하고자 하는 최소 시도 횟수

시작
    [eggs+1, floors+1] 크기의 2차원 배열(행렬) 정의
    i := 1부터 eggs까지 반복:
        minTrial[i, 1] := 1      // 1층에서는 시도 1회
        minTrial[i, 0] := 0      // 0층에서는 시도 불필요
    j := 1부터 floors까지 반복:
        minTrial[1, j] := j      // 계란이 1개면 j층까지 순차적으로 확인
    i := 2부터 eggs까지 반복:
        j := 2부터 floors까지 반복:
            minTrial[i, j] := 무한대(∞)
            k := 1부터 j까지 반복:
                res := 1 + max(minTrial[i-1, k-1], minTrial[i, j-k])
                만약 res < minTrial[i, j]이면, minTrial[i, j] := res
    minTrial[eggs, floors] 값 반환
종료

점화식의 직관적 이해

이 알고리즘의 핵심은 k번째 층에서 계란을 떨어뜨렸을 때 발생할 수 있는 두 가지 경우를 모두 고려하는 것입니다.

계란이 깨지는 경우: 사용 가능한 계란이 하나 줄어들고(i-1개), 확인해야 할 범위는 k층 아래의 k-1개 층으로 좁혀집니다 → minTrial[i-1][k-1]
계란이 깨지지 않는 경우: 계란은 그대로 i개이며, 이제 k층 위의 j-k개 층만 확인하면 됩니다 → minTrial[i][j-k]

최악의 경우를 기준으로 답을 구해야 하므로 두 값 중 큰 값(max)을 선택하고, 현재 시도 1회를 더합니다. 가능한 모든 k에 대해 이 값을 계산한 뒤 그중 최솟값을 취하면, 그것이 바로 해당 상태의 최소 시도 횟수입니다. 이 알고리즘의 시간 복잡도는 O(계란 수 × 층수²)입니다.

C 언어 구현 예제

#include<stdio.h>
#define MAX_VAL 9999

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, i, j, k;
    for (i = 1; i <= eggs; i++) { //1층은 시도 1회, 0층은 시도 0회
        minTrial[i][1] = 1;
        minTrial[i][0] = 0;
    }
    for (j = 1; j <= floors; j++) //계란이 1개면 각 층마다 j번의 시도 필요
        minTrial[1][j] = j;
    for (i = 2; i <= eggs; i++) { //계란이 2개 이상인 경우
        for (j = 2; j <= floors; j++) { //2층 이상인 경우
            minTrial[i][j] = MAX_VAL;
            for (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;
    printf("Enter number of eggs: ");
    scanf("%d", &egg);
    printf("Enter max Floor: ");
    scanf("%d", &maxFloor);
    printf("Minimum number of trials: %d", eggTrialCount(egg, maxFloor));
    return 0;
}

실행 결과

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