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

[문제] 
5가지 종류(A ~ E)의 캔디가 각각 6개씩 있다.
이 캔디들을 포장지로 포장을 하려고 하는데, 모든 캔디에 대해서 포장지와 내용물이 서로 일치하지 않도록 포장하고자 한다.
이때 가능한 가짓수는?
단, 포장재는 같은 포장재라도 각각 바코드가 있어서 서로 구별이 가능하나, 캔디는 같은 맛끼리는 구별이 안된다고 하자.
아래 그림 참조. Case1과 Case2는 서로 다른 케이스로 친다.
(대문자는 포장재, 소문자는 캔디)

 
[알고리즘]
우선은 A1, A2, ... 등을 구분하지 않고 A, B, C, D, E 라는 바구니가 있다고 하자.
각 바구니에 6개의 캔디를 담는데, A 바구니에는 a를 넣지 않고, B 바구니에는 b를 넣지 않는다. C, D, E도 마찬가지.
이렇게 담을 수 있는 케이스를 5 x 5 행렬에 저장하기로 한다.
예를 들어, A 바구니에 b 사탕 4개, c 사탕 1개, e 사탕 1개를 담았다면, A행은 { 0, 4, 1, 0, 1 }이 된다.

나머지 행도 동일하게 채울 수 있다.
[예시]

행렬을 채울 때 몇 가지 제약 조건이 필요하다.
1) matrix[n][n] = 0이어야 한다.
2) 각 바구니에 담긴 사탕 개수는 당연히 6개여야 한다.
3) 각 사탕의 총 개수도 6개여야 한다.
4) E행을 채울 때 e사탕의 개수는 0이어야 한다.
그리고 A ~ D행을 위 조건에 맞게 채웠다면 E 행은 자동으로 정해진다.
 
만약 행렬을 모두 채웠다면, 즉 바구니에 사탕을 모두 담았다면, 이제 본격적으로 포장 작업을 시작한다.
A 바구니에 b 사탕 4개, c 사탕 1개, e 사탕 1개가 있을 때 이를 포장하는 가짓수는
6! / (4! * 1! * 1!) 이다. (같은 것이 있는 순열의 개수)
마찬가지로 B ~ E 행에 대해서도 가짓수를 구할 수 있고, 이를 모두 곱해주면 된다.
A : 6! / (4! * 1! * 1!)
B: 6! / (3! * 3!)
C: 6! / (4! * 1! * 1!)
D: 6! / (5! * 1!)
E : 6! / (2! * 2! * 1! * 1!)
count = A * B * C * D * E
 
이제, 가능한 모든 행렬들에 대해서 위 카운트 값들을 구해서 더해 나가면 된다.
 
아래는 코드.
정답이 무지막지하게 크기 때문에 unsigned long long 으로 지정한다.

#include <stdio.h>
#define KIND 5
#define N 6

int remain[KIND] = { 0 };		// 사탕 종류 별로 남은 개수 저장
int matrix[KIND][KIND] = { 0 };	
int cnt[KIND] = { 0 };			// 각 바구니에 담긴 사탕 개수 저장
unsigned long long factorial[N + 1] = { 1, 1 };
unsigned long long count = 0;

void solve(int wrapper, int candy);
unsigned long long calCnt(int arr[][KIND]);
void printMatrix(int arr[][KIND]);
int main() {
    // remain 배열 초기화
    for (int i = 0; i < KIND; i++) {
        remain[i] = N;
    }
    // 팩토리얼 배열 채우기
    for (int i = 2; i <= N; i++) {
        factorial[i] = i * factorial[i - 1];
    }

    int wrapper = 0;
    int candy = 0;
    solve(wrapper, candy);
    printf("count = %llu\n", count);
}

void solve(int wrapper, int candy) {
	
    if (wrapper == KIND - 1) {
        // 마지막 행인데 마지막 종류 캔디가 남아 있으면 리턴
        if (remain[KIND - 1] != 0)
            return;
        // 마지막 행은 자동으로 남는 캔디들로 채워짐
        int check = 0;	// 남는 캔디가 N개인지 체크
        for (int i = 0; i < KIND; i++) {
            matrix[wrapper][i] = remain[i];
            check += remain[i];
        }
        if (check != N)
            return;
        count += calCnt(matrix);
        return;
    }
    // 행이 모두 차면, cnt = N인지 확인 후 다음 행으로 이동
    if (candy == KIND) {
        if (cnt[wrapper] != N)
            return;
        solve(wrapper + 1, 0);
        return;
    }

    for (int i = 0; i <= remain[candy]; i++) {
        if ((wrapper == candy) && (i != 0))
            continue;
        if (cnt[wrapper] + i > N)
            continue;
        matrix[wrapper][candy] = i;
        cnt[wrapper] += i;
        remain[candy] -= i;

        solve(wrapper, candy + 1);

        matrix[wrapper][candy] = 0;
        cnt[wrapper] -= i;
        remain[candy] += i;
    }
    return;
}
unsigned long long calCnt(int arr[][KIND]) {
    unsigned long long value = 1;
    for (int i = 0; i < KIND; i++) {
        unsigned long long temp = 1;
        for (int j = 0; j < KIND; j++) {
            temp *= factorial[arr[i][j]];
        }
        temp = factorial[N] / temp;
        value *= temp;
    }
    return value;
}
void printMatrix(int arr[][KIND]) {
    for (int i = 0; i < KIND; i++) {
        for (int j = 0; j < KIND; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

 
아래는 정답.
수는 크지만 계산 속도는 1초 미만으로 걸린다.

 
 
위 코드로도 계산 속도는 나쁘지 않지만 조금 더 단축시킬 수 있는 방법이 있다.
matrix 행렬의 제일 첫 행이 { 0, 4, 1, 0, 1 }일 때와 { 0, 1, 4, 0, 1} 일 때, 동형이기 때문에 가짓수는 동일하게 나온다.
즉, 아래 각 행렬의 가짓수는 결국 동일하다.
따라서 제일 첫행은 오름차순으로 정렬된 경우(아래 그림에서 제일 오른쪽 처럼)에 대해서만 탐색한 뒤

 
중복된 가짓수를 곱해주면 된다.
위 예시처럼 { 0, 0, 1, 1, 4 }라면 중복된 가짓수는 총 4! / (1! * 2! * 1!) = 12가지이다.
만약 { 0, 0, 0, 0, 6 } 이라면 중복된 가짓수는 총 4! / (3! * 1!) = 4가지이다. 
위 중복된 가짓수를 구하는 함수 dupCnt 를 추가로 정의하여 반영한 코드는 다음과 같다.
(solve, calCnt 수정, dupCnt 함수 추가)

void solve(int wrapper, int candy) {

    if (wrapper == KIND - 1) {
        // 마지막 행인데 마지막 종류 캔디가 남아 있으면 리턴
        if (remain[KIND - 1] != 0)
            return;
        // 마지막 행은 자동으로 남는 캔디들로 채워짐
        int check = 0;	// 남는 캔디가 N개인지 체크
        for (int i = 0; i < KIND; i++) {
            matrix[wrapper][i] = remain[i];
            check += remain[i];
        }
        if (check != N)
            return;
        count += calCnt(matrix);
        return;
    }
    // 행이 모두 차면, cnt 값 확인 및 초기화 후 다음 행으로 이동
    if (candy == KIND) {
        if (cnt[wrapper] != N)
            return;
        solve(wrapper + 1, 0);
        return;
    }

    for (int i = 0; i <= remain[candy]; i++) {
        if ((wrapper == candy) && (i != 0))
            continue;
        if (cnt[wrapper] + i > N)
            continue;
        // 첫 행이 오름차순인 경우만 탐색
        if (wrapper == 0 && candy > 0) {
            if (i < matrix[wrapper][candy - 1])
                continue;
        }
        matrix[wrapper][candy] = i;
        cnt[wrapper] += i;
        remain[candy] -= i;

        solve(wrapper, candy + 1);

        matrix[wrapper][candy] = 0;
        cnt[wrapper] -= i;
        remain[candy] += i;
    }
    return;
}
unsigned long long calCnt(int arr[][KIND]) {
    unsigned long long value = 1;
    for (int i = 0; i < KIND; i++) {
        unsigned long long temp = 1;
        for (int j = 0; j < KIND; j++) {
            temp *= factorial[arr[i][j]];
        }
        temp = factorial[N] / temp;
        value *= temp;
    }
    value *= dupCnt(arr[0]);
    return value;
}
int dupCnt(int* arr) {
    int freq[N + 1] = { 0 };
    for (int i = 1; i < KIND; i++) {
        freq[arr[i]]++;
    }
    int cnt = factorial[KIND - 1];
    for (int i = 0; i <= N; i++) {
        cnt /= factorial[freq[i]];
    }
    return cnt;
}

순식간에 정답이 나온다.