델라노이 수(Delannoy Number)란? C++로 델라노이 수를 구하는 프로그램 작성하기

델라노이 수(Delannoy Number)란?

델라노이 수는 직사각형 격자에서 남서쪽 모서리 (0, 0)에서 북동쪽 모서리 (a, b)까지 이동할 때, 동쪽(→), 북동쪽(↗), 북쪽(↑) 세 가지 방향의 이동만 허용했을 경우 만들어지는 경로의 총 개수를 나타내는 수입니다.

델라노이 수는 다음과 같은 점화식으로 정의할 수 있습니다.

D(a, b) = D(a-1, b) + D(a, b-1) + D(a-1, b-1)  (단, D(0, 0) = 1)

예를 들어, 델라노이 수 D(3, 3)의 값은 63입니다.

델라노이 수를 구하는 알고리즘

• 두 좌표 (a, b)를 입력값으로 받습니다.
• 정수형 함수 generateDelannoy(int a, int b)가 좌표 'a'와 'b'를 매개변수로 받아 처리합니다.
• 기저 사례(Base Case): 좌표 'a' 또는 'b'가 0이면 1을 반환합니다.
• 재귀 사례: 그 외의 경우에는 점화식 D(a-1, b) + D(a, b-1) + D(a-1, b-1)을 이용해 델라노이 수를 계산하고 그 결과를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int generateDelannoy(int a, int b){
    int d = 1;
    if((a == 0) || (b == 0)){
        d = 1;
    } else {
        d = generateDelannoy(a-1, b) + generateDelannoy(a, b-1) + generateDelannoy(a-1, b-1);
    }
    return d;
}

int main(){
    int a = 3;
    int b = 3;
    int result = 0;
    result = generateDelannoy(a, b);
    cout << result << endl;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

63

주어진 좌표 (a, b) = (3, 3)에 대해 점화식 D(a-1, b) + D(a, b-1) + D(a-1, b-1)을 적용하면 델라노이 수 63이 출력됩니다.

참고: 효율성 개선

위 재귀 방식은 중복 계산이 많아 입력값이 커지면 실행 시간이 급격히 늘어날 수 있습니다. 실제 프로젝트에서는 메모이제이션(Memoization)이나 동적 계획법(DP)을 함께 사용하면 시간 복잡도를 O(a×b)로 크게 줄일 수 있습니다.