99클럽 코테 스터디 41일차 TIL + 오늘의 학습 키워드 1137. N번째 트리보나치 수

ㅎㅇ·2024년 8월 31일
0

항해99 TIL

목록 보기
33/33

⭐ 문제

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

🧐 시도

N번째 트리보나치 수 계산

class Solution {
public int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;

    int[] trib = new int[n + 1];
    trib[0] = 0;
    trib[1] = 1;
    trib[2] = 1;
    
    for (int i = 3; i <= n; i++) {
        trib[i] = trib[i-1] + trib[i-2] + trib[i-3];
    }
    
    return trib[n];
}

}

📝 풀이

기본 케이스를 처리합니다: n이 0이면 0을 반환하고, n이 1 또는 2이면 1을 반환합니다.
n+1 크기의 배열을 생성하여 트리보나치 수열의 값을 저장합니다.
처음 세 값(0, 1, 1)을 초기화합니다.
3부터 n까지 반복하면서 이전 세 값의 합을 계산하여 새로운 값을 구합니다.
최종적으로 n번째 트리보나치 수를 반환합니다.

이 방법은 시간 복잡도 O(n)과 공간 복잡도 O(n)을 가집니다. 주어진 제약 조건(0 <= n <= 37)을 만족하며, 32비트 정수 범위 내에서 계산이 가능합니다.
이 해결책을 사용하면 예시에서 주어진 입력값들에 대해 다음과 같은 결과를 얻을 수 있습니다:

n = 4일 때, tribonacci(4) = 4
n = 25일 때, tribonacci(25) = 1389537

profile
안녕하세요

0개의 댓글