d[i] = i번째 계단을 왼발로 밟아서 끝나는 경우의 수 i번째 계단을 오른발로 밟고 끝나는 경우의 수는 d[i-1]이므로 d[i]만 계산해놓으면 됩니다.

d[i] = d[i-1] (오른발0칸 + 왼발1칸) + d[i-2] (오른발0칸 + 왼발2칸) + d[i-3] (오른발0칸 + 왼발3칸) +d[i-2] (오른발1칸 + 왼발1칸) + d[i-3] (오른발1칸 + 왼발2칸) + d[i-4] (오른발1칸 + 왼발3칸)

이므로, 이 점화식을 잘 계산하면 됩니다. 답은 d[n] + d[n-1]이 됩니다.

C++은 긴자리수에 대한 표현이 영 안좋아서 n=52일 때에 대한 답을 구하는게 최선인데 만약 긴자리수를 아주 편하게 쓸 수 있는 python이나 JAVA같은 친구들을 사용하면 n=50,000 정도까지는 의미있는 시간 내에 계산할 수 있지 않을까 싶습니다. 물론 아래 코드로 구현한 O(n)짜리 보통의 방법으론 안되고 행렬의 제곱으로 푸는 O(log n)짜리를 사용해서 겨우겨우...

#include<stdio.h>
int n;
unsigned long long int d[1009];
int main()
{
    int i, j, k;
    scanf("%d", &n);
    if (n>52) { printf("Too Big!\n"); }
    d[0] = 1;
    d[1] = 2;
    d[2] = 5;
    d[3] = 12;
    for (i = 4; i <= n; i++) {
        d[i] = d[i - 1] + 2 * d[i - 2] + 2 * d[i - 3] + d[i - 4];
    }
    printf("%llu\n", d[n] + d[n-1]);
}

Python 3.7

pichulia님 코드를 참고해서 python으로 구현했습니다.

def sta(n):
    a = [1, 2, 5, 12] + [0]*(n-3)
    i = 4
    while i <= n:
        a[i] = a[i-1] + 2*a[i-2] + 2*a[i-3] + a[i-4]
        a[i-4] = 0
        i += 1
    return a[n]+a[n-1]

a[i-4] = 0 부분은 큰 수 계산을 위해서 넣었습니다. 넣지 않았을 경우 sta(200000)을 계산할 때 메모리를 3기가 먹습니다. 공간복잡도 O(n²)

아래는 리스트 대신 변수를 사용한 식입니다.

def sta(n):
    if n < 4:
        a = [1, 2, 5, 12]
        return a[n]+a[n-1]
    a, b, c, d = 12, 5, 2, 1
    i = 4
    while i <= n:
        a, b, c, d = a + 2*b + 2*c + d, a, b, c
        i += 1
    return a + b

계산은 sta(100000) = 1.3초, sta(200000) = 5.5초, sta(400000) = 22초 정도 걸립니다.(cpu 성능에 따라 다릅니다.)

이 코드들은 루프가 1개라서 O(n)처럼 보이지만, n이 2배 증가할 때 연산값의 자릿수(log)가 2배씩 증가하여 실제 시간복잡도는 O(n²)이 됩니다.

def stair(n):
    START, LEFT, RIGHT = 'Start', 'Left', 'Right'
    que = [[(0, START, 0)]]
    cnt = 0

    while que:
        seq = que.pop(0)
        stride, foot, pos = seq[-1] # last step

        if n < pos:
            continue

        if n == pos:
            print([step[:2] for step in seq[1:]])
            cnt += 1
            continue

        if foot in (START, LEFT):
            que.append(seq + [(0, RIGHT, pos + 0)])
            que.append(seq + [(1, RIGHT, pos + 1)])

        if foot in (START, RIGHT):
            que.append(seq + [(1, LEFT, pos + 1)])
            que.append(seq + [(2, LEFT, pos + 2)])
            que.append(seq + [(2, LEFT, pos + 3)])

    print(cnt)

C 재귀함수를 이용하여 작성해보았습니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

unsigned long long int advance(int n, int curr, bool leftFoot);

int main() {
    int n;

    printf("n을 입력하세요: ");
    scanf("%d", &n);

    printf("경우의 수: %llu", advance(n, 0, true) + advance(n, 0, false));

    return 0;
}

unsigned long long int advance(int n, int curr, bool leftFoot) {
    // 맨 밑일 때 curr == 0, 도착하는 순간 curr == n

    // 현재 위치가 n보다 큰 경우 유효하지 않은 움직임
    if (curr > n) {
        return 0;
    }

    // 현재 위치가 n과 같은 경우 성공적인 경우의 수 중 하나
    if (curr == n) {
        return 1;
    }

    unsigned long long int result = 0; // 최종 return되는 경우의 수

    if (leftFoot == true) {
        // 왼발로 오름
        result += advance(n, curr + 1, false);
        result += advance(n, curr + 2, false);
        result += advance(n, curr + 3, false);
    }
    else {
        // 오른발로 오름
        result += advance(n, curr, true);
        result += advance(n, curr + 1, true);
    }

    return result;
}

ㅎㅎ 재미있네요. 요구사항대로 그냥 C 언어입니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int     N_Case=0;

void limp(char *sSteps, char cLastStep, int n_todo) {
int     i;
char    *sNextSteps;
        if (n_todo==0) {
                printf("%s\n", sSteps);
                ++N_Case;
        }
        if (n_todo<=0)
                return;
        sNextSteps = (char*)malloc(strlen(sSteps)+3);
        if (cLastStep!='L')
                for (i=1; i<=3; i++) {
                        sprintf(sNextSteps,"%s L%d", sSteps, i);
                        limp(sNextSteps, 'L', n_todo-i);
                }
        if (cLastStep!='R')
                for (i=0; i<=1; i++) {
                        sprintf(sNextSteps,"%s R%d", sSteps, i);
                        limp(sNextSteps, 'R', n_todo-i);
                }
        free(sNextSteps);
}

int main() {
int     n;
        printf("Number (>0) ? ");
        scanf("%d", &n);
        limp("", ' ', n);
        printf("%d cases.\n", N_Case);
}

파이썬으로도 해보았습니다..

def Limp(steps, laststep, n_todo):
    global Case
    if (n_todo==0):
        print(steps)
        Case = Case+1
    if (n_todo<=0):
        return
    if (laststep!='왼'):
        for left in range(1,4):
            next_steps = steps.copy()
            next_steps.append('왼'+str(left))
            Limp(next_steps, '왼', n_todo-left)
    if (laststep!='오'):
        for right in range(0,2):
            next_steps = steps.copy()
            next_steps.append('오'+str(right))
            Limp(next_steps, '오', n_todo-right)

N = int(input('자연수: '))
Case = 0
Limp([],' ',N)
print("총", Case, "경우")