리트코드 - 1137. N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/

N-th Tribonacci Number - LeetCode

트리보나치 수열 Tn이 다음과 같을 때:

n >= 0일 때 T0 = 0, T1 = 1, T2 = 1, Tn+3 = Tn + Tn+1 + Tn+2입니다.
n이 주어지면 Tn의 값을 반환한다.

 

재귀적으로 푸는 것과 dp를 활용하는 풀이 중 고민하다가 dp를 활용하는 풀이를 선택했다.

길이가 0, 1, 2일때는 값이 정해져 있으므로 정해진 값을 반환하도록 하고.

 

트리보나치 연산 값을 저장하는 배열 sequence를 선언하고 One pass로 순회하면서 연산하고 배열에 값을 저장했다.

이후 해당 배열의 마지막 인덱스를 확인하면 답을 구할 수 있다.

 

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:  # O(1)
            return 0
        elif n == 1 or n == 2:  # O(1)
            return 1
        sequence = [0 for _ in range(n + 1)]  # O(n)
        sequence[1], sequence[2] = 1, 1
        for i in range(3, n + 1):  # O(n)
            sequence[i] = sequence[i - 1] + sequence[i - 2] + sequence[i - 3]
        return sequence[n]

 

시간 복잡도

입력 값의 크기가 n이라고 할 때 리스트를 선언할 때와 해당 리스트를 순회할 때 시간 복잡도가 O(n)이므로 시간 복잡도는 O(n)이다.

 

공간 복잡도

트리보나치 연산 값을 저장하기 위한 n 크기의 리스트를 생성해야하므로 공간복잡도는 O(n)이다.