[HACKERRANK] - Recursion: Davis' Staircase

www.hackerrank.com/challenges/ctci-recursive-staircase/problem

Recursion: Davis' Staircase | HackerRank

한 번에 1, 2, 3칸씩 계단을 오를 수 있을 때, 계단을 오르는 모든 경우의 수의 개수를 구하는 문제.

 

<My Solution>

 

계단 수 n, 경우의 수 f(n)

f(1) = [1]

f(2) = [11, 2]

f(3) = [111, 12, 21, 3]

 

계단이 4개 이상일 때 부터는 오를 수 있는 칸 수가 [1,2,3] 이므로, 세 가지 경우로 나누어 생각할 수 있다.

마지막에 1칸을 올라 4번째 계단을 밟았을 경우: f(3) + [1] = [1111, 121, 211, 31]

마지막에 2칸을 올라 4번째 계단을 밟았을 경우: f(2) + [2] = [112, 22]

마지막에 3칸을 올라 4번째 계단을 밟았을 경우: f(1) + [3] = [13]

 

마찬가지로 5번째, 6번째, ... n번째 오를 수 있는 경우의 수 f(n) = f(n-1) + f(n-2) + f(n-3) 으로 정리할 수 있다.

def stepPerms(n):
    c = [0,0,1]
    for i in range(n):
        c[0], c[1], c[2] = c[1], c[2], sum(c)
    return c[2]

 

<Recursion>

Recursion으로도 풀 수 있다.

 

풀이는 아래와 같다.

cache = dict()
def stepPerms(n):
    if n==0: return 1
    if n<0: return 0

    if n in cache: return cache[n]
    cache[n] = stepPerms(n-1)+stepPerms(n-2)+stepPerms(n-3)
    return cache[n]