c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q51 과자로 장난하기 (두번째 방법)

[문제] 

5가지 종류(A ~ E)의 캔디가 각각 6개씩 있다.

이 캔디들을 포장지로 포장을 하려고 하는데, 모든 캔디에 대해서 포장지와 내용물이 서로 일치하지 않도록 포장하고자 한다.

이때 가능한 가짓수는?

단, 포장재는 같은 포장재라도 각각 바코드가 있어서 서로 구별이 가능하나, 캔디는 같은 맛끼리는 구별이 안된다고 하자.

아래 그림 참조. Case1과 Case2는 서로 다른 케이스로 친다.

(대문자는 포장재, 소문자는 캔디)

 

 

[알고리즘]

책에서 소개한 방법으로 상당히 멋있는 방법이다.

알고리즘 자체는 간단하다.

A1부터 E6까지 순차적으로 포장을 하되, A에는 a가 오지 않게, B에는 b가 오지 않게... 포장을 하면 된다.

(포장의 순서는 A1->B1->C1->...A2->B2->C2->... 로 하기로 한다.)

단, 그냥 단순히 그렇게만 하면, 탐색의 가짓수가 너무나 많다. 각 포장지마다 올 수 있는 캔디 종류가 5가지이므로 대략 5의 30제곱 만큼 (물론 사탕 개수 제한이 있어서 그보다는 적긴 하지만) 탐색을 해야 하므로... 이는 불가능한 방법이다.

책에서는 메모화 기법을 사용했다.

캔디의 남는 개수를 remain 배열에 저장한다. 

예를 들어, remain = { 6, 6, 6, 6, 6 }이면 a ~ e 캔디 모두 6개씩 남아 있다는 뜻이고 (즉, 제일 처음 시작 포인트)

remain = { 4, 3, 4, 1, 0 }이라면 a는 4개, b는 3개, c는 4개, d는 1개, e는 0개 남았다는 뜻이다.

(총 18개 캔디가 포장되고, 12개 캔디가 남았다.)

그리고, remain 상태일 때 포장할 수 있는 가짓수를 cnt(remain)이라고 하자.

 

먼저 A1에 b 캔디를 포장했다고 하자. 그러면 remain 배열은 당연히 { 6, 5, 6, 6, 6 }이 되고, 이 때의 가짓수를 cnt({6, 5, 6, 6, 6})이라 하자. 이는 A1에 b캔디가 포장된 상태에서, 나머지 포장지에 캔디를 포장하는 총 가짓수이다.

 

마찬가지로 A1에는 c, d, e 캔디가 올 수 있으므로

cnt({6, 6, 6, 6, 6}) = cnt({6, 5, 6, 6, 6}) + cnt({6, 6, 5, 6, 6}) + cnt({6, 6, 6, 5, 6}) + cnt({6, 6, 6, 6, 5})이다.

cnt({6, 6, 6, 6, 6})이 결국 궁극적으로 구하고자 하는 정답이다.

 

다시 cnt({6, 5, 6, 6, 6})을 살펴보자.

A1에 b 캔디를 포장한 상태에서 이번에는 B1을 포장한다고 하자. B1에 a캔디가 올 수도 있고, c, d, e 캔디가 올 수도 있다.

즉, cnt({6, 5, 6, 6, 6}) = cnt({5, 5, 6, 6, 6}) + cnt({6, 5, 5, 6, 6}) + cnt({6, 5, 6, 5, 6}) + cnt({6, 5, 6, 6, 5})이다.

이런식으로 반복해 나간다.

이 풀이의 핵심은 모든 remain 배열에서의 cnt 가짓수를 메모화하여 저장하는 것이다.

예를 들어, A1에 c캔디가 포장되고, B1에 d캔디가 포장된 상태라면 remain = { 6, 6, 5, 5, 6 }이다.

이때의 cnt({6, 6, 5, 5, 6}) 값을 구하여 memo에 기록해뒀다고 하자.

그리고 탐색을 계속 해나가면 언젠가

A1에 d캔디가 포장되고, B1에 c 캔디가 포장되는 경우가 등장하게 되는데

이 때도 역시나 remain = { 6, 6, 5, 5, 6 }이다.

우리는 이미 cnt({6, 6, 5, 5, 6})을 알고 있으므로!!! 이 이후의 C1 ~ E6을 확인하는 과정을 생략할 수 있다.

즉, 탐색 수가 엄청나게 줄어든다. 

위 2가지 케이스는 동일 가짓수를 가진다.

 

아래는 이를 반영한 코드이다.

remain 배열을 7진수 숫자라고 보고 이를 10진수로 변환하여, memo 배열의 index로 활용한다.

예를 들어 remain = { 4, 3, 2, 2, 6 }이라면 이를 43226이라는 7진수로 보고 이를 10진수로 변환하면 10751이 된다.

따라서 memo[10751]에 cnt({4, 3, 2, 2, 6})을 저장한다.

#include <stdio.h>
#define F 5
#define N 6
#define SZ (N + 1)
unsigned long long memo[16807] = { 0 };	// 7*7*7*7*7

unsigned long long solve(int* remain, int num);
int trans(int* arr);
int main() {
    int remain[F] = { 0 };
    unsigned long long int count = 0;
    int num = 0;			// 포장된 캔디 개수
    for (int i = 0; i < F; i++)
        remain[i] = N;

    count = solve(remain, num);
    printf("count = %llu\n", count);
}
unsigned long long solve(int* remain, int num) {
    if (num == F * N) {		// 캔디를 모두 포장하면
        return 1;
    }
    int index = trans(remain);
    if (memo[index])
        return memo[index];	// 저장된 값이 있으면 활용한다

    unsigned long long cnt = 0;
    for (int i = 0; i < F; i++) {
        if (remain[i] == 0)
            continue;
        // num = 0, 5, 10, 일 때는(A포장지를 포장할 때) i가 0이 되면 안됨
        // num = 1, 6, 11, 일 때는(B포장지를 포장할 때) i가 1이 되면 안됨
        if (num % F == i)
            continue;

        remain[i]--;
        cnt += solve(remain, num + 1);
        remain[i]++;
    }
    memo[index] = cnt;
    return memo[index];	
}
// 배열을 숫자로 변환
int trans(int* arr) {
    int num = 0;
    for (int i = 0; i < F; i++) {
        num = (N + 1)* num + arr[i];
    }
    return num;
}

 

이 역시 정답이 순식간에 구해진다.