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

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

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

 

 

[알고리즘] 책에서 소개한 방법으로 상당히 멋진 풀이 방법이다.

n개의 세로 선이 있고, 어떤 패턴에 대해서 최소 가로선으로 사다리를 만들었다고 하자.

여기에 세로 선 1개를 추가로 넣는다. 추가로 넣는 것은 n + 1가지 방법이 가능하다.

예를 들어 n = 3이라고 하고 여기에 세로 선 1개를 추가하여 n = 4로 만들었다고 하자.

4가 들어갈 수 있는 자리는 총 4가지가 가능하다.

1) 4를 맨 우측에 넣은 경우 : 추가되는 가로 선은 0개이다.

2) 4를 1과 3 사이에 넣는 경우 : 추가되는 가로 선은 1개이다.

3) 4를 2와 1 사이에 넣는 경우 : 추가되는 가로 선은 2개이다.

4) 4를 맨 좌측에 넣는 경우 : 추가되는 가로 선은 3개이다.

다른 패턴에 대해서도 동일하다.

아래 패턴에서도 동일하게 4를 넣는 위치에 따라서 추가되는 가로 선 개수가 정해진다.

 

f(n, line) : n 개의 세로 선이 있고, line(최소 가로 선) 개의 가로 선을 그을 때 만들 수 있는 패턴의 가짓수라고 정의하자.

n = 4인 경우, 4를 놓는 위치에 따라서 최대 0 ~ 3개까지 가로 선이 증가하므로 다음과 같이 구할 수 있다.

f(4, 0) = f(3, 0)

f(4, 1) = f(3, 0) + f(3, 1)

f(4, 2) = f(3, 0) + f(3, 1) + f(3, 2)

f(4, 3) = f(3, 0) + f(3, 1) + f(3, 2) + f(3, 3)

f(4, 4) = f(3, 1) + f(3, 2) + f(3, 3) + f(3, 4)

f(4, 5) = f(3, 2) + f(3, 3) + f(3, 4) + f(3, 5)

f(4, 6) = f(3, 3) + f(3, 4) + f(3, 5) + f(3, 6)

f(4, 7) = f(3, 4) + f(3, 5) + f(3, 6) + f(3, 7)

... 이렇게 구할 수 있다.

 f(3, 0) = 1, f(3, 1) = 2, f(3, 2) = 2, f(3, 3) = 1, f(3, 4) = f(3, 5) = ... = 0이므로

f(4, 0) = 1

f(4, 1) = 1 + 2 = 3

f(4, 2) = 1 + 2 + 2 = 5

f(4, 3) = 1 + 2 + 2 + 1 = 6

f(4, 4) = 2 + 2 + 1 = 5

f(4, 5) = 2 + 1 = 3

f(4, 6) = 1

f(4, 7) = f(4, 8) = .... = 0이 된다.

 

일반화 하면

f(n, line) = f(n - 1, line - n + 1)) + f(n - 1, line - n + 2) + f(n - 1, line - n - 3) + ... + f(n - 1, line) 이다.

그리고 f(2, 0) = 1, f(2, 1) = 1이다.

아래는 코드.

#include <stdio.h>
#define N 7
#define L 10
#define SZ (N * (N - 1) / 2)

int main() {
    int cnt[N + 1][SZ + 1] = { 0 };
    cnt[2][0] = 1, cnt[2][1] = 1;

    for (int n = 3; n <= N; n++) {
        int max = (n * (n - 1)) / 2;
        for (int line = 0; line <= max; line++) {
            int min = line - (n - 1) < 0 ? 0 : line - (n - 1);
            for (int j = min; j <= line; j++) {
                cnt[n][line] += cnt[n - 1][j];
            }
        }
    }
    printf("cnt = %d\n", cnt[N][L]);
}

 

상당히 간결할 뿐만 아니라, 속도도 상당히 빠르다.

f(7, 10) = 573

 

f(20, 10)일 때도 즉시 구해진다.

 

아래는 동적 메모리를 할당하여 cnt[n]마다 배열의 크기를 다르게 가져간 경우.

#include <stdio.h>
#include <stdlib.h>
#define N 7
#define L 10
#define SZ (N * (N - 1) / 2)

typedef unsigned long long ull;
int main() {

    ull** cnt = NULL;
    cnt = (ull**)malloc(sizeof(ull*) * (N + 1));
    for (int n = 0; n <= N; n++) {
        int max = (n * (n + 1)) / 2;
        cnt[n] = (ull*)malloc(sizeof(ull) * (max + 1));
        for (int i = 0; i <= max; i++) {
            cnt[n][i] = 0;
        }
    }	
    cnt[2][0] = 1, cnt[2][1] = 1;

    for (int n = 3; n <= N; n++) {
        int max = (n * (n - 1)) / 2;
        for (int line = 0; line <= max; line++) {
            int min = line - (n - 1) < 0 ? 0 : line - (n - 1);
            for (int j = min; j <= line; j++) {
                cnt[n][line] += cnt[n - 1][j];
            }
        }
    }
    printf("cnt = %llu\n", cnt[N][L]);

    for (int n = 0; n <= N; n++) {
        free(cnt[n]);
    }
    free(cnt);
}