[백준/python] 9095: 1,2,3더하기

9095번: 1, 2, 3 더하기

 

숫자들을 5까지 계산해보면 직전 3개까지의 합이라는 걸 알 수 있다.

왜냐면 우리가 쓸 수 있는 수는 1,2,3 3가지이고, 이전에 썼던 것에 대해 1차이 나면 뒤에 1을 더해주기, 2차이 나면 2를 더해주기 3차이나면 3을 더해주기...로 해결되기 때문이다. 뒤에더하든 앞에더하든 아무튼 한 쪽 방향으로 쭉 더해줘야 중복이 나오지 않는다 

def main():

    t = int(input())

    arr = [0 for _ in range(11)]

    # print(arr)

    arr[1] = 1

    arr[2] = 2

    arr[3] = 4

    def dp(k):

        if arr[k] == 0:

            arr[k] = dp(k-1)+dp(k-2)+dp(k-3)

            return arr[k]

        else:

            return arr[k]

    for _ in range(t):

        n = int(input())

        print(dp(n))