2021-11-20 출근하는 방법

 

위의 계단의 위치를 생각해보면, 

1->2->3->4

2->3->4

1->3->4

2->4 

이다.

 

즉 4번째 계단에 도착하려면 2번째 계단이나 3번째 계단에서 출발해야한다.

식을 쓰면 stair(4) = stair(3) + stair(2)이고 이 식은 피보나치 식과 같다.

 

def staircase(n):
    
    temp1, temp2 = 1, 1
    for i in range(n):
        temp1, temp2 = temp2, temp1+temp2
    return temp1

 

 

계단 올라가는 수를 조정한다면?

 

 

 

이 경우에도 마찬가지로 stair[n] 을 올라가려면 stair[n-k] + stair[n-l] + --- 이런 식이다.

def staircase(stairs, possible_steps):
    container = [1,1]
    for height in range(2, stairs + 1):
        container.append(0)
        
        for stair in possible_steps:
            if height - stair >= 0:
                container[height] += container[height-stair]
    return container[stairs]

 

2021-11-20