C#으로 작성했습니다.

        public int CountStairSteps(int n, int j)
        {
            var count = 0;
            for (int i = n - 1; i >= j; i--)
            {
                if (j == 0) break;
                count += Fibonacci(i);
                j--;
            }
            return count;
        }

        public int Fibonacci(int n)
        {
            var first = 0;
            var second = 1;
            for (int i = 1; i <= n; i++)
            {
                var temp = first;
                first = second;
                second += temp;
            }
            return second;
        }

점화식, 피보나치, 수분할

j=int(input('한 번에 올라가는 max계단 : '))
n=int(input('전체 계단의 수 : '))

s=[]
for i in range(j):
    s.append(2**i)

for i in range(n-j):
    s.append(sum(s))
    s.remove(s[0])
    #print(s)
print()
print('계단을 올라가는 경우의 수는 %d' %s[j-1])

피보나치를 재귀함수로 구현했습니다.

def getSteps(n, j): 
    if n <= j :
        return 2**(n-1)

    total = 0
    for x in range(1,j+1):
        total += getSteps(n-x, j)
    return total

n=int(input('전체 계단수 : '))
j=int(input('한 번에 올라가는 최대 계단수 : '))

print ("총 경우의 수 :", getSteps(n,j))

메모이제이션을 사용한 재귀로 구현해봤습니다.

var m = [];
function d(n, j) {
    if (n <= j) {
        return Math.pow(2, n - 1);
    } else if (m[n]) {
        return m[n];
    } else {
        m[n] = 0;
        for (var i = j; i > 0; i--) { 
            m[n] += d(n - i, j);
        }
        return m[n];
    }
}

console.log(d(10, 3));

맞는지 모르겠네요...

def memoize(f):
    cache = dict()
    def inner(*n):
        if n in cache:
            return cache[n]
        r = f(*n)
        cache[n] = r
        return r
    return inner

@memoize
def steps(n, j):
    if n <= j:
        return 2**(n-1)
    return sum([steps(x, j) for x in list(range(n-1, 0, -1))])

C 언어

잘몰라서, Brute Force로 했네요, 다풀고 다른분들 정답을 보니 이게 피보나치 라는걸 알았네요. 휴우...

피보나치는 풀이가 많으니까 저는 Brute Force 예제로 올리죠... 좀 부끄럽긴 해도...

n=5, j = 3 이라면 f(5) = f(4) + f(3) + f(2);

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

f(3) = f(1) + f(2) + 1;

f(2) = f(1) + 1;

f(1) = 1; 첫번째 계단을 오르는 경우의수

f(2) = 2; 두번째 계단을 오르는 경우의수 (1,1) (2)

f(3) = 4; 세번째 계단을 오르는 경우의수 (1,1,1) (1,2) (2,1) (3)

f(4) = 7; 네번째 계단을 오르는 경우의수 (1,1,1,1) (2,1,1) (1,2,1) (1,1,2) (2,2) (3,1) (1,3)

f(5) = 13; 다섯번째 계단을오르는 겨우의수는 2번째 +3, 3번째 + 2, 2번째 +1 하는 경우 므로 f(4) + f(3) + f(2)

모든 경우의 수를 다도는 방법 --;;(brute force)

계단이 5개이고 3계단 까지 오르는 경우를 5자리 4진수로 생각하고 모든 4진수 5자리를 다 뿌려봄. 그중에서 중간에 0이 있거나 시작이 0인 경우는 제외하고 끝에 0이 1개이상있는 경우는 괜찮음. 그 자리수의 합이 5가 되는 조합을 모두 출력.

#include <stdio.h>
void base(int b, int v, int* a, int n){
    for(int i = 0; i < n; i++){
        a[i] = 0;
    }
    if(v == 0){
        return;
    }
    int i = 0;
    while(v > 0){
        a[i] = (v % b);
        v /= b;
        i++;
    }
}

int main()
{
    int n = 5, j = 3;

    long t = 1;
    int a[n];

    for(int i = 0; i < n; i++){
        t *= (j + 1); 
    }

    for(int i = 0; i < t; i++){
        int s = 0;
        int isZeroContained = 0;
        int isZeroContinue = 0;

        base((j + 1), i, a, n);

        for(int j = 0; j < n; j++){
            if(a[j] == 0 && isZeroContained == 0){
                isZeroContained = 1, isZeroContinue = 1;
            }
            if(isZeroContained == 1 && a[j] != 0){
                isZeroContinue = 0;
            }
            s += a[j];
        }

        if(s == n){
            if(isZeroContained == 1 && isZeroContinue == 0){
                continue;
            }
            for(int j = 0; j < n; j++){
                printf("%d ", a[j]);
            }
            printf("\n");
        }
    }
}

D:\16.minGW>a
3 2 0 0 0
2 3 0 0 0
3 1 1 0 0
2 2 1 0 0
1 3 1 0 0
2 1 2 0 0
1 2 2 0 0
1 1 3 0 0
2 1 1 1 0
1 2 1 1 0
1 1 2 1 0
1 1 1 2 0
1 1 1 1 1

D:\16.minGW>

C++ Code

메모이제이션을 이용해서 작성해봤습니다.

#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 

int cache[31][31]; 

int solve(int n,int j){
    // n: 계단 수, j: 한번에 올라갈 수 있는 최대 계단 수 
    if (n == 0) return 1;  
    if (j == 1) return 1;  
    int &ret = cache[n][j];  
    if (ret != -1) return ret; 
    ret = 0;  
    for (int steps = 1; steps <= j; steps++){
        if (n-steps >= 0){
            ret += solve(n-steps,j);  
        }
    }
    return ret;  
}  

int main(){
    memset(cache,-1,sizeof(cache)); 
    int n,j;  
    scanf("%d %d",&n,&j); 
    printf("%d\n",solve(n,j)); 
    return 0;  
}

include

include

using namespace std;

int multy1(int m,int n){

int i;

int sum=1;

for(i=0;i<m;i++){
                 sum=sum*(n);
                 }
return (sum-1)/(n-1);

}

int count1(int *a){ int i; int sum=0; i=0; while(a[i]!=0){ sum++; i++; } return sum; }

int main(int argc, char *argv[]) { int i,j,k;

int m,n;

int sum=0;

int count=0;


int a[100]={0,};

int end=0;

scanf("%d %d",&m,&n);

i=0;

printf("%d\n",multy1(m,n));

while(i!=multy1(m,n)){

                       a[0]++;



                       for(j=0;j<m;j++){
                                        if(a[j]>n){
                                                   a[j]=1;
                                                   a[j+1]++;

                                                   }


                                        }

                       end=count1(a);

                       sum=0;
                        for(k=0;k<end;k++){

                                           sum=sum+a[k];

                                           }
                       if(sum==m){
                                 count++;

                                   for(k=0;k<end;k++){
                                                     printf("%d ",a[k]);
                                                     }


                                   printf("\n");

                                   }

                       i++;


                       }

printf("%d\n",count);

system("PAUSE");
return EXIT_SUCCESS;

}

#include <stdio.h>
#include <math.h>
int fib(int n);

int j;
void main(void) {
    int n=5;
    j=3;
    printf("%d", fib(n));
}

int fib(int n) {
    if(n<=j)
        return pow(2.0, n-1);

    int sum = 0;
    for(int i=1; i<j+1; i++)
        sum = sum + fib(n-i);
    return sum;
}

def stairway(n, j):
        if n == 0:
                return 1
        else:
                x = 0
                for i in range(1, j+1):
                        if n >= i:
                                x += stairway(n-i, j)
                return x

def find_2nd(T,num):
    if num == 2:
        return T[0]
    elif num == 3:
        return T[1]
    else:
        while num != 4:
            num -= 1
            T = [T[1],sum(T)]
        return sum(T)

def find_num(index):
    c,tmp,result = 1,2,3
    for x in range(3,index+1):
        tmp += (c*3)
        result += tmp
        c += 1
    return result

N, _max = list(map(int,input().split(' ')))
step, T = 1, [2,3]
for x in range(N-1):
    step += step

if N-_max == 0:
    print(step)
elif _max == 2:
    print(find_2nd(T,N))
elif N-_max == 1:
    print(step-1)
elif N-_max == 2:
    print(step-2)
elif _max == 1:
    print(1)
else:
    print(step-find_num(N-_max))

#### 2017.02.04 D-383 ####

엉망진창....

import java.util.Stack;

public class Stairs {

    static int k = 0;
    static Stack<Integer> l = new Stack();

    public static void main(String[] args) {
        recursive(5, 3);
        System.out.println("===================");
        System.out.println(k);
    }

    private static void recursive(int n, int m) {
        if (n == 0) {
            k = k + 1;
            System.out.println(l);
            return;
        }
        if (n < 0) {
            return;
        }
        for (int i = 1; i <= m; i++) {
            l.push(i);
            recursive(n - i, m);
            l.pop();
        }
    }
}

1. 피보나치수열을 이용하지 않고 조합을 이용함.
2. 경우의 수를 찾는 방법은 brute force임.
3. count는 m계단씩 오르는 갯수를 구한 리스트이며, 경우의 수를 셀때 사용됨.

#113. 계단오르기

import math

def in_p(list1,list2):
    if len(list1) != len(list2):
        return 'Inner product must be used by two same length list'
    else: #len(list1) == len(list2)
        sum = 0
        for i in range(len(list1)):
            sum += list1[i]*list2[i]
        return sum

n = int(input('계단의 갯수 :'))
m = int(input('한번에 올라갈 수 있는 계단 수 :'))
x = 0
step = []
count = []
ways = [] #D==0인 count를 저장
for i in range(m):
    step.append(i+1) #step=[1,...,m]
    count.append(0) #count=[0,...,0]

#m칸씩 올라가는게 몇번인가 구하는 과정
while(m*count[m-1]<= n):
    D = in_p(step,count) - n
    if D>0:
        if x != m-1:
            x+=1
        count[x]+=1
        for i in range(x):
            count[i]=0
    elif D==0:
        ways.append(count[:]) #count[:]를 하지 않으면 ways에 변수 count가 저장됨...
        if x != m-1:
            x+=1
        count[x]+=1
        for i in range(x):
            count[i]=0
    else: #D<0
        x=0
        count[x]+=1

#계산파트
result = 0
for i in range(len(ways)):
    denominator = 1
    for j in range(m):
        denominator = denominator * math.factorial(ways[i][j])
    result += math.factorial(sum(ways[i]))/(denominator)

print(int(result))

def advFibo(n,step):
    l=[0,1]
    if n == 0 or n == 1: return l[n]

    while len(l) <= step:
        l.append(sum(l)+1)
    if n >= step:
        while len(l)-1 != n:
            l.append(sum(l[::-1][:step]))
    return l[n]

javascript

var climbing = function (n, j) {
    cache = [0, 1];
    for (let i = 2; i <= j; i++) {
        cache[i] = cache.reduce((a, b) => a + b, 0) + 1;
    }    

    return (function climb(n, j) {
        if (typeof cache[n] === "undefined") {
            cache[n] = Array.from(Array(j), (v, i) => n - i - 1)
                            .filter(v => v > 0)
                            .map(v => climb(v, j))
                            .reduce((a, b) => a + b, 0);
        }
        return  cache[n];
    })(n, j);
};

var steps = climbing(5, 3);
console.log(steps);

DP

def steps(n, j):
    prec = [0] * (j - 1) + [1]
    for i in range(n):
        prec = prec[1:] + [sum(prec)]

    return prec[-1]

Ruby

def walk_up_cases(n, j)
  Hash.new { |h,k| h[k] = k < 0 ? 0 : (k == 0 ? 1 : (k-j...k).sum(&h)) }[n]
end

Test

expect(walk_up_cases(1, 5)).to eq 1
expect(walk_up_cases(5, 3)).to eq 13
expect(walk_up_cases(9, 2)).to eq 55
expect(walk_up_cases(100, 3)).to eq 180396380815100901214157639

def f(n, j):
    sum = 0
    if n > j:
        for i in range(1, j+1):
            sum += f(n-i, j)
        return sum
    else:
        return 2**(n-1)


for i in range(1, 10):
    print(i, f(i, 3))

파이썬 3.6

"""
아이디어>
 1) 계단수(n)가 1 또는 0일때, j에 상관없이 경우의 수는 1입니다.
  : j가 1일때는 경우의 수는 n과 상관없이 1입니다.
 2) 계단수(n)가 2일때, j가 1보다 클 때 경우의 수는 2가 됩니다.
 3) 계단수(n)가 3이상일 때의 경우의 수는 (n-1)+ㆍㆍㆍ(n-j)이 됩니다.
    ex) case(n=3,j=3) = case(3-1) + case(3-2) + case(3-3) = 2 + 1 + 1 = 4
    ex) case(n=3,j=2) = case(3-1) + case(3-2) = 2 + 1 = 3
"""

# 피보나치 수열 응용
def upcases(n,j):
    case,t = [1,1],2
    while t <= n:
        if t < j: 
# t(현재 계단의 위치)가 j(한번에 이동 가능한 계단의 수)보다 낮을 때 이전 위치의 모든 경우의 수의 합이 현재 위치에서의 경우의 수가 됩니다.
            case.append(sum(case))
            t += 1
        else: 
            case.append(sum(case[(len(case)-j):]))
            t += 1
    print(case[-1])

if __name__ == "__main__":
    n,j= map(int,input('').split())
    upcases(n,j)

• 결과값

3 2
3

3 3
4 3

5 4
15

5 5
16

5 6
16

6 3
24

100 3
180396380815100901214157639

def stair(n, j):
    result = 0
    if n == 0:
        result += 1
    elif n < j:
        for i in range(n):
            result += stair(i, j)
    else:
        for i in range(j):
            result += stair(n-1-i, j)
    return result

library(dplyr)
StairClimb <- function(x){
  tmplist <- list()
  for(i in 1:(x-1)){
    tmplist[[i]] <- combn(1:x,i)[,apply(combn(1:x,i), 2, sum) == x]
  }
  return(
    tmplist[tmplist %>% lapply(function(x) if(length(x)>=1) return(T) else return(F)) %>% unlist]
  )
}
StairClimb(5)  
[[1]]
[1] 5

[[2]]
     [,1] [,2]
[1,]    1    2
[2,]    4    3

dplyr library는 chaining을 위한 패키지입니다. combn으로 모든 조합을 만들고 열별로 합친 후 input값과 같으면 반환하는 방식입니다.

memo = {}
def func(n, r):
    result = 0
    if (n,r) not in memo:
        for i in range(1,r+1):
            if n-i > 0: result += func(n-i,r)
            else:       result += 1; break
        memo[(n,r)] = result
    return memo[(n,r)]

print(func(10,5))

n이 0인 경우 함수값을 1, n이 1인 경우 함수값을 0로 정해두면
모든 n과 j에 대해 예외없이 일반화된 식으로 표현할 수 있습니다.

def f(n,j):
  if n == 0: return 1
  if n < 0: return 0
  _sum = 0
  for i in range(n-j, n): _sum += f(i, j)
  return _sum

print(f(6,3))

파이썬 3입니다

특정 계단까지 오르는 경우는 그 이전 계단 j개에서 오르는 경우의 합이므로 (a_n = a_n-1 + a_n-2 + ... + a_n-j 꼴이다)

이를 이용하여 점화식을 작성했습니다.

n = int(input())
j = int(input())


def rec_f(n0, j0):
    case = 0
    if n0 == 0 or n0 == 1:
        return 1
    else:
        for i in range(min(n0, j0)):
            case += rec_f(n0 - i - 1, j0)
    return case


print(rec_f(n, j))

def stairway(N, J) :
    queue, res = [[i+1] for i in range(J)], []

    while len(queue) != 0 :
        fst = queue.pop(0)
        if sum(fst) == N : 
            res.append(fst) ## 계단을 모두 올랐을 경우 : print
            continue
        for st in range(1, J+1) :
            if sum(fst)+st <= N :
                queue.append(fst+[st])
    return len(res)
print(stairway(5, 3))

queue를 이용하였습니다.

결과

13

// Rust

// 재귀함수

fn step_rising() {

let (n, j) = (5, 3);
println!("{}", f(n, j));

} fn f(n: usize, j: usize) -> usize {

if n == 1 || n == 0 { 1 }
else {
    let mut result = 0;
    let mut l = j;
    if n < j { l = n;}
    for i in 1..=l { result += f(n-i, j); }
    result
}

}