[Hackerrank] [Medium] Recursion: Davis' Staircase

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

Recursion: Davis' Staircase | HackerRank

풀이

• 계단을 1칸, 2칸, 3칸 올라갈 수 있을 때, n을 입력으로 받았을 때 가능한 모든 경우의 수 찾는 문제.
• 재귀함수로 풀지 않고, memoization으로 풀 수 있음.
• bottom-up으로 풀었고, 식은 next_step = next_step-1 + next_step-2 + next_step-3 경우의 수를 더해줌.
  • 한 칸을 올라갈 수 있기 때문에 (next_step - 1)의 경우에 수에 마지막 1칸이 붙게 되고,
  • (next_step - 2) 경우의 수에 마지막 2칸, (next_step - 3) 경우의 수에 마지막 3칸이 붙으면 됨.

def stepPerms(n):
    count_dict = {}
    n1, n2, n3 = 1, 2, 3
    count_dict[1] = 1
    count_dict[2] = 2
    count_dict[3] = 4
    while n not in count_dict.keys():
        next_num = n3 + 1
        count_dict[next_num] = count_dict[next_num - 1] + count_dict[next_num - 2] + count_dict[next_num - 3]
        n3 = next_num 

    return count_dict[n]