c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q54 공평하게 나눈 케이크

[문제]

W * H 크기의 직사각형 모양 케이크가 있다. 두 사람이 이 케이크를 번갈아가며 칼질하여 두 부분으로 나뉜 것 중 작은 것을 먹는다.

위 그림과 같이 두 사람이 같은 양의 케이크를 먹도록 칼질을 한다고 할 때, 칼과 케이크가 만나는 단면의 길이를 가장 짧게 하고자 한다. 예를 들어 위 그림에서는 단면의 길이가 4 + 3 + 3 + 1 + 1 = 12이다.

아래 그림은 4 x 5 케이크를 공평하게 자르는 3가지 케이스에 대해서 단면의 길이가 서로 다름을 보여준다.

첫번째 예시는 4/4/3/3/2/2/1 = 19, 두번째 예시는 5/3/3/3/1/1 = 16, 세번째 예시는 4/4/4/1/1/1 = 15

16 x 12 케이크를 공평하게 자를 때 최소 단면의 길이는?

 

 

[알고리즘]

1) minCut(w, h, q) 함수를 정의한다. 

w와 h는 케이크의 크기이다.

q는 최종적으로 케이크를 모두 자른 후에 선공인 (먼저 케이크를 자른) A가 후공인 B 보다 더 많이 가지는 케이크 양을 가리킨다.

공평하게 잘라야 한다면 q = 0이어야 한다.

A가 B보다 3개 더 많이 가지도록 잘라야 한다면 q = 3이 된다. 반대로 A가 B보다 3개 덜 가져야 한다면 q = -3이 된다.

minCut(w, h, q)는 w * h 케이크에 대해 q를 가지도록 최소 단면 길이로 자를 때 그 길이 값을 리턴한다.

결국 문제에서 구하고자 하는 것은 minCut(16, 12, 0)이다. 

 

2) 먼저 minCut(5, 4, 0)에 대해서 살펴보자.

minCut(5, 4, 0)은 다음 4가지 케이스 중 최소 값을 가진다.

 

i) 4(단면 길이) + minCut(4, 4, 4)

A가 4를 가져갔으므로, 남은 케이크에서는 선공인 B가 4개를 더 가져가야 한다. 따라서 q = 4이다.

ii) 4(단면 길이) + minCut(3, 4, 8)

A가 8을 가져갔으므로, 남은 케이크에서는 선공인 B가 8개를 더 가져가야 한다. 따라서 q = 8.

또한, 3 x 4나 4 x 3이나 동일하므로 w >= h가 되도록 한다. (나중에 메모화를 위한 목적)

4 + minCut(4, 3, 8)

마찬가지 방법으로

iii) 5(단면 길이) + minCut(5, 3, 5)

iv) 5(단면 길이) + minCut(5, 2, 10)

 

그런데 위 케이스에서 iv)는 불가능하다. 5 x 2 케이크에서 선공이 10개를 모두 가지는 것은 불가능하기 때문.

따라서 i) ~ iii) 중 최소값을 구하면 된다.

 

3) minCut(4, 4, 4)는 다시 다음 2가지 케이스 중 최소값이다. (가로로 자르는 것은 세로로 자르는 것과 동형이다)

i) 4 + minCut(4, 3, 0)

선공이 4개를 더 많이 먹어야 하는 상황에서 4조각을 취했으므로, 남은 케이크에 대해서는 공평하게 잘라야 한다. 따라서 q = 0

ii) 4 + minCut(4, 2, 4)

선공이 4개를 더 많이 먹어야 하는 상황에서 8조각을 취했으므로, 남은 케이크에 대해서는 선공이 4개를 더 먹어야 한다.

 

4) 이런 식으로 반복해 나가다보면 결국엔 minCut(1, 1, 1)에 도달하는데 minCut(1, 1, 1) = 0으로 정의하면 된다.

 

이를 코드로 구현하면 다음과 같다. (메모화X)

GARBAGE는 miinCut이 절대로 가질 수 없는 큰 값이면 된다.

#include <stdio.h>
#include <math.h>
#define W 16
#define H 12
#define GARBAGE ((W - 1) * H + W * (H - 1))

int minCut(int w, int h, int q);
int max(int val1, int val2);
int min(int val1, int val2);
int main() {
    int result = minCut(W, H, 0);
    if (result == GARBAGE) {
        printf("%d x %d에서는 공평하게 자를 수 없습니다.\n", W, H);
    }
    else {
        printf("minCut = %d번\n", result);
    }
}
int minCut(int w, int h, int q) {
    if (w == 1 && h == 1) {
        if (q == 1)
            return 0;
        else
            return GARBAGE;
    }
    if (w * h <= abs(q)) {
        return GARBAGE;
    }

    int minValue = GARBAGE;

    // 세로로 자르기
    for (int i = 1; i <= w / 2; i++) {
        int new_w = max(w - i, h);
        int new_h = min(w - i, h);
        int newValue = h + minCut(new_w, new_h, -q + h * i);
        minValue = minValue > newValue ? newValue : minValue;
    }

    // 가로로 자르기
    for (int j = 1; j <= h / 2; j++) {
        int new_w = max(w, h - j);
        int new_h = min(w, h - j);
        int newValue = w + minCut(new_w, new_h, -q + w * j);
        minValue = minValue > newValue ? newValue : minValue;
    }
    return minValue;
}
int max(int val1, int val2) {
    return val1 > val2 ? val1 : val2;
}
int min(int val1, int val2) {
    return val1 < val2 ? val1 : val2;
}

이렇게 하면 답은 구해지는데, 시간이 수 분 이상 소요된다.

minCut(w, h, q)는 사실 똑같은 값들이 굉장히 많이 호출되므로, 이 값들을 메모화하면 시간을 크게 단축시킬 수 있다.

 

파이썬에서는 튜플 (w, h, q) 를 딕셔너리의 키로, minCut(w, h, q)를 딕셔너리의 값으로 하여 쉽게 메모화할 수 있으나, C언어에서는 그럴 수 없기 때문에 3차원 배열을 활용하기로 한다.

memo[max(w, h)][min(w, h)][2 * w * h - 1]

w >= h로 하기로 했으므로 위와 같이 지정한다.

또한, q가 가질 수 있는 값은 -w*h < q < w*h 이므로 메모의 크기는 2*w*h - 1로 해준다.

q가 음수일 수도 있으므로 q + offset을 배열의 인덱스로 활용한다.

0 <= q + offset < 2 * w * h - 1

메모화가 반영된 코드는 아래와 같다.

#include <stdio.h>
#include <math.h>
#define W 16
#define H 12
#define MAX(A, B) A > B ? A : B
#define MIN(A, B) A < B ? A : B
#define OFFSET (W * H - 1)
#define GARBAGE ((W - 1) * H + W * (H - 1))

int memo[MAX(W, H)][MIN(W, H)][2 * W * H - 1] = { 0 };

int minCut(int w, int h, int q);
int main() {
    int result = minCut(MAX(W, H), MIN(W, H), 0);
    if (result == GARBAGE) {
        printf("%d x %d에서는 공평하게 자를 수 없습니다.\n", W, H);
    }
    else {
        printf("minCut = %d\n", result);
    }
}
int minCut(int w, int h, int q) {
    if (memo[w][h][q + OFFSET])
        return memo[w][h][q + OFFSET];
    if (w == 1 && h == 1) {
        if (q == 1)
            return 0;
        else
            return GARBAGE;
    }
    if (w * h <= abs(q)) {
        return GARBAGE;
    }

    int minValue = GARBAGE;
    int newValue;
    // 세로로 자르기
    for (int i = 1; i <= w / 2; i++) {
        newValue = h + minCut(MAX(w - i, h), MIN(w - i, h), -q + h * i);
        minValue = minValue > newValue ? newValue : minValue;
    }

    // 가로로 자르기
    for (int j = 1; j <= h / 2; j++) {
        newValue = w + minCut(MAX(w, h - j), MIN(w, h - j), -q + w * j);
        minValue = minValue > newValue ? newValue : minValue;
    }
    memo[w][h][q + OFFSET] = minValue;
    return minValue;
}

정답은 47

 

메모화를 이용하면 30 x 30에 대해서도 순식간에 답을 구할 수 있다.

30 x 30일 때 정답