[2024] day 116. Leetcode 1137. N-th Tribonacci Number

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 24일 (수)
Leetcode daily problem

1137. N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/?envType=daily-question&envId=2024-04-24

Problem

트리보나치 수열 Tn은 다음과 같이 정의된다.
n >= 0인 경우 T0 = 0, T1 = 1, T2 = 1,
Tn+3 = Tn + Tn+1 + Tn+2이다.
n이 주어지면 Tn의 값을 반환한다.

Solution

dynamic programming

해당 문제는 재귀적인 방법으로 n번째 트리보나치 수를 찾는 것이 아니라, 반복적인 방법을 사용하여 해결해야 한다.
이 문제를 해결하기 위해서는 동적 계획법(Dynamic Programming)을 사용해서 해결해야 하는데, 주어진 n에 대해 반복문을 사용하여 처음부터 n번째까지의 트리보나치 수를 계산하고, 그 중 n번째 수를 반환하는 방식으로 문제를 해결할 수 있다.

예를 들어, 입력값으로 4가 주어졌을 때, 트리보나치 수열은
0, 1, 1, 2, 4, 7, 13, ...이고, 4번째 수는 2이다.

Code

class Solution:
    def tribonacci(self, n: int) -> int:
        if n <2:
            return n
        dp = [0, 1, 1]
        
        for i in range(3, n+1):
            val = dp[0] + dp[1] + dp[2]
            dp[0], dp[1], dp[2] = dp[1], dp[2], val
            
        return dp[2]

Complexicity

시간 복잡도

주어진 n을 순환하므로 시간복잡도는 O(n) 이다.

공간 복잡도

공간복잡도는 상수개의 변수만 사용하므로 O(1) 이다.