[LeetCode] - 1137. N-th Tribonacci Number

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "N-th Tribonacci Number" 문제입니다.

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

 

문제 : 

The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

---

Example 1 :

Input : n = 4

Output : 4

Explanation : T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4

 

Example 2 :

Input : n = 25

Output : 1389537

 

Constraints :

• 0 <= n <= 37
• The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

---

이 문제에서 Tribonacci 수열 Tn은 다음과 같이 정의됩니다: T0 = 0, T1 = 1, T2 = 1, 그리고 n >= 0에 대해 Tn+3 = Tn + Tn+1 + Tn+2. 주어진 n에 대해 Tn의 값을 반환하는 문제입니다. 예를 들어, n=4인 경우, T4는 4입니다.

피보나치수열이랑 로직은 똑같은 셈이죠.

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
}

 

이 코드는 주어진 정수 n에 대해 Tribonacci 수열의 n번째 값을 계산합니다. Tribonacci 수열은 T0 = 0, T1 = 1, T2 = 1로 시작하고, 그 이후의 값은 이전 세 값의 합으로 정의됩니다. 이 코드는 동적 계획법을 사용하여 효율적으로 값을 계산합니다.

 

1. 기본 케이스 처리 :
   • n이 0인 경우 0을 반환합니다.
   • n이 1 또는 2인 경우 1을 반환합니다.
2. 동적 계획법 배열 초기화 :
   • n+1 크기의 배열을 생성하고 초기값을 설정합니다.
3. 반복문을 통한 값 계산 :
   • 3부터 n까지의 Tribonacci 수열 값을 계산하여 dp 배열에 저장합니다.
4. 결과 반환 :
   • dp 배열의 n번째 값을 반환합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • O(n) : 3부터 n까지 반복문을 통해 값을 계산하므로 시간 복잡도는 O(n)입니다.
2. 공간 복잡도:
   • O(n) : dp 배열을 사용하여 n+1개의 값을 저장하므로 공간 복잡도는 O(n)입니다.

이 코드는 동적 계획법을 사용하여 효율적으로 Tribonacci 수열의 값을 계산합니다. 각 단계에서 이전 세 단계의 값을 더하여 현재 값을 결정하는 방식으로, 피보나치수열보다 한 단계 더 복잡한 구조를 가지고 있습니다. 이 문제 또한 DP를 사용해야 했다는 점, 기억해 두시고요! DP가 알고리즘 문제에 되게 많이 나오는 것 같습니다.

---

내 코드 Runtime 결과