[leetcode] 1137. N-th Tribonacci Number

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

---

T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3)

n이 주어질 때, T(n) 값을 구해라.

---

n크기의 배열을 만들어서 문제에서 주어진 점화식으로 구할 수 있다.

이 경우, 시간/공간 복잡도는 모두 O(n)이 된다.

 

점화식을 보면 결국 필요한 값들은 최신 값 3개 이므로 크기가 3인 배열(let, arr)을 만들고

arr[n%3] = arr[0] + arr[1] + arr[2] 

위 식으로 arr을 채워나간 뒤 n번째까지 모두 채우면 arr[n%3] 가 정답이 된다.

이 경우 시간복잡도는 동일하게 O(n)이지만 공간복잡도는 O(1)이 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1137.%20N-th%20Tribonacci%20Number.cpp