8.1 트리플 스텝

문제 

어던 아이가 n개의 계단을 오른다. 한 번에 1계단 오르기도 하고 2계단이나 3계단을 오르기도 한다. 계단을 오르는 방법이 몇가지가 있는지 계산하는 프로그램을 구현하라.

 

접근법

n번째 계단을 딛기 바로 직전에 마지막에 딛는 계단은 3계단전, 2계단전, 1계단전에 있었을 것이다. 

따라서, n개의 계단을 오르는 모든 경로를 생각해 본다면 1계단, 2계단 3계단 전까지의 경로를 단순히 더해주면 될 것이다.

무식하게 재귀로 구현할 수 있겠지만 반복적으로 호출되는 함수가 많아서 비효율적일 것이다.

따라서 메모이제이션을 통해 좀 더 효율적으로 해결 할 수 있다.

def Solution(n):
    memo = [-1]* (n+1)
    return countWay(n, memo)


def countWay(n, memo):
    if n < 0 :
        return 0
    if n == 0 :
        return 1
    if meno[n] > -1 :
        return memo[n]
    return countWay(n-1,memo) + countWay(n-2, memo) + countWay(n-3, memo)

 

근데 위의 코드를 봤을때 사실 현재 위치로부터 3번째 전, 2번째 전, 1번째 전의 값을 더해주는 것이기 때문에 

피보나치와 거의 접근 법이 비슷하고, 3번째전, 2번째 전, 1번째 전의 값만 가지고 있으면 항상 n번째까지의 경우의 수를 구할 수 있으므로

3개의 변수만을 가지고도 해결할 수 있을 것 같다. 

def Solution(n):
    third = 0
    secound = 0
    first = 1
    for i in range(n):
        third = secound
        secound = first
        first = first + secound + third
    return first