[leetcode] 1137. N-th Tribonacci Number

문제

주어진 문제는 Tribonacci 수열에서 n번째 항의 값을 구하는 것입니다. Tribonacci 수열은 이전 3개의 항을 더한 값으로 다음 항을 계산하는 특징을 가지고 있습니다.

 

풀이

주어진 문제를 해결하기 위해 다이나믹 프로그래을 활용할 수 있습니다. 다이나믹 프로그래밍은 중복되는 계산을 피하기 위해 계산 결과를 저장하여 재활용하는 기법입니다.

 

 

Tribonacci 수열의 n번째 항의 값을 구하기 위해 다음과 같은 접근 방식을 사용합니다:

1. 초기값 설정: dp 리스트를 생성하고 초기값으로 dp[0] = 0, dp[1] = 1, dp[2] = 1을 설정합니다.
2. 반복문을 통한 값 계산: dp[i] = dp[i-3] + dp[i-2] + dp[i-1]을 반복문을 통해 계산하여 dp[n]의 값을 구합니다.
3. 결과 반환: dp[n]을 반환하여 n번째 항의 값을 얻습니다.

시간 복잡도는 O(n)입니다. 반복문을 통해 n개의 항에 대해 값을 계산하므로, 입력 값 n에 선형적으로 비례하여 실행 시간이 증가합니다.

공간 복잡도는 O(n)입니다. 입력 값 n에 비례하는 크기의 dp 리스트를 생성하고 사용하므로, 공간 복잡도가 선형적으로 증가합니다.

 

코드

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n + 1):
            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]

        return dp[-1]

 

참고

• 1137. N-th Tribonacci Number