[알고리즘] N 계단 오르기

1. 문제 정의

---

100개의 계단이 있으며 나는 한 번에 10개의 계단을 오를 수 있는 능력을 가지고 있다.

 

이 때, 100개의 계단을 올라갈 수 있는 경우의 수는 몇 개인가?

 

2. 해결 코드

---

문제를 보고 생각할 수 있는 가장 초기의 코드를 작성한 것이다.

stairs = 100
skill = 10
table = [0 for i in range(stairs+1)]
table[0] = 1

for i in range(1, stairs+1):
    s=0
    for j in range(1,skill+1):
        if i-j<0:
            t=0
        else:
            t= table[i-j]
        s = s+t
    table[i] = s
print (table[stairs])

 

2. 초기 코드를 확인 후 줄일 수 있는 부분을 확인 후, 파이썬의 강점을 살려 개선 코드를 작성한 것이다

stairs = 100
skill = 10
table = [0 for i in range(stairs+1)]
table[0] = 1

for i in range(1, stairs+1):
    s=0
    for j in range(1,skill+1):
        t=(table[i-j],0)[i-j<0]
        s = s+t
    table[i] = s
print (table[stairs])

 

3. 개선 코드를 작성 후 하나의 함수로 만듦으로써 n 계단 오르기를 구현한 것이다.

def climbing(staris, skill):
    table = [0 for i in range(stairs + 1)]
    table[0] = 1
    for i in range(1, stairs+1):
        s=0
        for j in range(1,skill+1):
            t=(table[i-j],0)[i-j<0]
            s = s+t
        table[i] = s
    return table[stairs]
r =  (climbing(100,10))
print (r)

 

4. 함수의 최적화와 코드의 최적화를 구현한 것이며 아래의 코드는 계단 오르기 문제에 있어 가장 최적화 된 코드이다.

def climbing(n,m):
    table=[0 for i in range(n+1)]
    table[0]=1
    for i in range(1,n+1):
        s=(i-m,0)[(i-m)<0]
        table[i]=sum(table[s:i])
    return table[n]
a=climbing(100,10)
print (a)