Problem :

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


My Solution :

#!/usr/bin/env python3


def stepPerms(n):
    steps = [1, 2, 4]
    if n < 4:
        return steps[n-1]
    for i in range(4, n):
        steps[(i-1) % 3] = sum(steps)
    return sum(steps)


s = int(input())
for _ in range(s):
    n = int(input())
    res = stepPerms(n)
    print(res)


Comment :

참고로 원래 문제에서 mod (10**9 + 7)을 요구하였지만, 적용하면 오히려 Test Case 3개가 틀렸다고 나오기 때문에 적용하지 않았다. 일단 제보는 해두었으니 나중에 Test Case가 수정되겠지...