계단 오르기

계단을 오르는 방법에는 여러가지가 있습니다. 한 계단씩만 올라가는 방법이 있고, 두 계단만 올라가는 방법이 있고 혹은 세 계단만 올라가는 방법이 있습니다.

계단의 수를 n이라 하고 한번에 올라갈 수 있는 maximum 계단의 수를 j라고 했을 때 계단을 올라갈 수 있는 경우의 수를 구하시오.

fibonacci
n=5, j = 3 이라면 다섯번째 계단을 오르는 경우의 수는 네번째 계단에서 1칸 오르는 것과. 세번째 계단에서 두칸오르는것 두번째 계단에서 세칸오르는 것이 있으므로 각각의 계단까지 가는 경우의 수의 합이다. 즉, 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; 다섯번째 계단을오르는 겨우의수는 f(4) + f(3) + f(2) - 이 종성, 2016/09/12 23:28 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

11개의 풀이가 있습니다. 1 / 2 Page

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])
+1 j>n 일 경우 결과값이 오류가 발생합니다. - Jung Seung-yong, 2016/08/04 11:04 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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

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

2016/11/19 21:07

fdn

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

fibonacci x 1

언어별 풀이 현황
전 체 x 11
cs x 1
python x 5
javascript x 1
cpp x 2
기 타 x 2