c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q55 사다리 타기의 가로 선 (첫번째 방법)

[문제] 7개의 세로 선이 있고, 여기에 가로 선들을 그어 사다리 타기를 만든다고 하자.
윗 숫자는 1, 2, 3, 4, 5, 6, 7 로 고정한다.
가로 선을 10개 그어서 만들 수 있는 패턴(아랫 숫자)의 가짓수는?
[예시1] 가로 선 10개를 그어서 나오는 패턴 중 1가지

단, 10개를 그어서 만들 수 있는 패턴이라고 하더라도, 그 보다 적은 수로도 만들 수 있는 패턴이라면 제외하기로 한다.
예를 들어 아래 그림의 패턴은 선 2개만으로도 구현할 수 있으므로 제외한다.

 
 
[알고리즘]
간단하게 n = 4인 경우에 대해서 먼저 살펴보기로 한다.
1) line = 0개인 경우: 패턴은 1234이다.
arr = { 1234 }
2) line = 1개인 경우 : line은 총 3군데에 그릴 수 있고 가능한 패턴은 2134, 1324, 1243이다.
arr = { 2134, 1324, 1243 }

잘 살펴보면 인접한 자릿수끼리 스왑이 된 것을 볼 수 있다.
이를 코드로 구현하면 다음과 같다.

ULL ghostLeg(ULL val, int pos) {	// ULL : unsinged long long
    ULL newVal = 0;
    int po = 1;
    for (int i = 0; i < N; i++) {
        if (i == pos)
            newVal += (val % 10) * po * 10;
        else if (i == pos + 1)
            newVal += (val % 10) * po / 10;
        else
            newVal += (val % 10) * po;

        val /= 10, po *= 10;
    }
    return newVal;
}

 
3) line = 2개인 경우: 이는 line = 1개 패턴으로부터 출발하면 된다.
예를 들어 2134에서 시작한다고 하자. 그러면 1234, 2314, 2143 3가지 패턴이 가능할 것이다.
단, 1234는 이미 앞에서 등장했으므로 제외하고 2314, 2143만 남게 된다.
이번에는 1324에서 시작한다고 하자. 그러면 3124, 1234, 1342 3가지 패턴이 가능한데 마찬가지로 1234는 제거한다.
마지막으로 1243에서 시작한다고 하자. 그러면 2143, 1423, 1234 3가지 패턴이 가능한데, 2143과 1234는 이미 등장한 패턴이므로 1423만 남게 된다.
최종적으로 { 2314, 2143, 3124, 1342, 1423 } 5가지만 남게 된다.
 
4) line = 3개인 경우: 이는 line = 2 패턴으로부터 출발하면 된다.
총 5 * 3 = 15가지 패턴이 가능한데, 앞서 등장한 것들을 제거하다 보면 최종적으로 6개만 남게 된다.
{ 3214, 2341, 2413, 3142, 1432, 4123 }
 
이런 식으로 line을 늘려 나가는 것이다.
아래는 n = 4일 때 결과

 
[메모화하기]
패턴이 이전에 등장했는지 여부를 저장하기 위해서 memo를 사용한다. (등장했다면 true, 미등장 상태라면 false)
그런데, 패턴 값을 그대로 메모의 인덱스로 사용하면 메모리 낭비가 너무 심하다.
실제로 1, 2, 3, 4로 표현할 수 있는 패턴의 가짓수는 24개에 불과한데, 패턴 값을 그대로 사용하려면 4321 + 1 개의 저장 공간이 필요하기 때문이다.
따라서 패턴 값을 다음과 같이 메모의 인덱스로 변환하는 과정이 필요하다.
1234 => 0
1243 => 1
1324 => 2
1342 => 3
...
4321 => 23
 
이는 다음과 같이 진행한다.
맨 앞 숫자가 1이라면 0 ~ 5까지 번호가 부여될 것이다. 맨 앞 숫자가 2라면 6 ~ 11까지 번호가 부여될 것이고,
맨 앞 숫자가 3이라면 12 ~ 17, 맨 앞 숫자가 4라면 18 ~ 23까지 번호가 부여될 것이다.
즉 간격은 3! = 6이다. 
이번에는 2번째 자릿수에 대해서 살펴보자. 예를 들어 맨 앞 숫자가 2라고 하면
21XX 는 (6 + 0) ~ (6 + 1) 번호가 부여될 것이고
23XX 는 (6 + 2) ~ (6 + 3) 번호가 부여될 것이고
24XX 는 (6 + 4) ~ (6 + 5) 번호가 부여될 것이다.
간격은 2!이다.
이런 식으로 번호를 부여하면 된다.
 
그러기 위해서
abcd 각 자릿수에서 우측에 자기 보다 작은 숫자의 개수가 몇 개인지를 파악한다.
1) 예를 들어 1234의 경우 1보다 작은 숫자는 없으므로 0, 2 보다 작은 숫자는 없으므로 0, 3 역시 0개이다. 따라서 [0, 0, 0]으로 표현한다.
2) 반대로 4321이라면 4보다 작은 숫자가 3개, 3보다 작은 숫자가 2개, 2보다 작은 숫자가 1개이므로 [3, 2, 1]로 표현할 수 있다.
3) 2413이라면 2보다 작은 숫자가 1개, 4보다 작은 숫자가 2개, 1보다 작은 숫자가 0개이므로 [1, 2, 0]으로 표현할 수 있다.
이제 배열의 각 숫자에 팩토리얼 값을 곱해서 번호를 구한다.
1) 예를 들어, [0, 0, 0]의 경우에는 0 * 3! + 0 * 2! + 0 * 1! = 0이다.
2) [3, 2, 1]의 경우에는 3 * 3! + 2 * 2! + 1 * 1! = 23이다.
3) [1, 2, 0]의 경우에는 1 * 3! + 2 * 2! + 0 * 1! = 10이다.
이를 코드로 구현하면 다음과 같다.

k번째 숫자를 구하는 법

int getIndex(ULL val) {
    int arr[N - 1] = { 0 };
    int index = 0;
    for (int i = 0; i < N - 1; i++) {
        int p = (val / (int)pow(10, N - 1 - i)) % 10;
        for (int j = i + 1; j <= N - 1; j++) {
            int q = (val / (int)pow(10, N - 1 - j)) % 10;
            if (p > q)
                arr[i]++;
        }
        index += facto[N - 1 - i] * arr[i];
    }
    return index;

 
아래는 전체 코드. 오랜만에 등장한 비재귀 풀이 방법이다.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 7
#define L 10

typedef unsigned long long ULL;

bool* memo = NULL;
ULL facto[N + 1] = { 1 };

void copy(ULL* arr1, ULL* arr2, int sz);
ULL ghostLeg(ULL val, int pos);
int getIndex(ULL val);
int main() {
    // 팩토리얼 배열 채우기
    for (int i = 1; i <= N; i++) {
        facto[i] = facto[i - 1] * i;
    }
    
    // 메모 동적메모리 할당 및 초기화
    memo = (bool*)malloc(sizeof(bool) * facto[N]);
    for (int i = 0; i < facto[N]; i++) {
        memo[i] = false;
    }
    
    // arr 배열 동적메모리 할당
    int cnt = 1;
    ULL* arr = (ULL*)malloc(sizeof(ULL) * cnt);
    ULL init = 0;
    for (int i = 1; i <= N; i++) {
        init = init * 10 + i;
    }
    arr[0] = init;
    memo[getIndex(init)] = true;


    for (int line = 1; line <= L; line++) {
        ULL* temp = (ULL*)malloc(sizeof(ULL) * cnt * (N - 1));
        int count = 0;

        for (int i = 0; i < cnt; i++) {
            for (int pos = 0; pos < N - 1; pos++) {
                int val = ghostLeg(arr[i], pos);
                int index = getIndex(val);
                if (memo[index])
                    continue;
                temp[count++] = val;
                memo[index] = true;
            }
        }
        free(arr);
        cnt = count;
        arr = (ULL*)malloc(sizeof(ULL) * count);
        copy(arr, temp, cnt);

        // 확인용 출력
        printf("line = %2d: cnt = %d   //   ", line, cnt);
        for (int i = 0; i < cnt; i++) {
            printf("%llu ", arr[i]);
        }
        printf("\n");


        free(temp);
	}
    free(arr);
    printf("num = %d\n", cnt);
}
void copy(ULL* arr1, ULL* arr2, int sz) {
    for (int i = 0; i < sz; i++)
        arr1[i] = arr2[i];
}
ULL ghostLeg(ULL val, int pos) {
    ULL newVal = 0;
    int po = 1;
    for (int i = 0; i < N; i++) {
        if (i == pos)
            newVal += (val % 10) * po * 10;
        else if (i == pos + 1)
            newVal += (val % 10) * po / 10;
        else
            newVal += (val % 10) * po;

        val /= 10, po *= 10;
    }
    return newVal;
}
int getIndex(ULL val) {
    int arr[N - 1] = { 0 };
    int index = 0;
    for (int i = 0; i < N - 1; i++) {
        int p = (val / (int)pow(10, N - 1 - i)) % 10;
        for (int j = i + 1; j <= N - 1; j++) {
            int q = (val / (int)pow(10, N - 1 - j)) % 10;
            if (p > q)
                arr[i]++;
        }
        index += facto[N - 1 - i] * arr[i];
    }
    return index;
}

 
n = 7일 때 line을 10개 그려서 만들 수 있는 패턴은 573개이다.
이렇게 하면 line 개수가 적을 때는 전체 탐색을 할 필요가 없으므로 속도가 빠르다.
 
아래 결과를 보면 대칭형인 것을 볼 수 있다.

n = 7일 때

 
아래는 n = 9일 때 정답