[DP]99클럽 코테 스터디 39일차 TIL + 1236-n-th-tribonacci-number

1236. N-th Tribonacci Number

Easy

---

The Tribonacci sequence T_n is defined as follows: 

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

 

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.

 

 

<내 코드>

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

        t[2] = 1
        if n < 3: return t[n]

        i = 3
        while i < n + 1:
            t[i] = t[i-3] + t[i-2] + t[i-1]
            i += 1
        return t[-1]

- DP를 푸는데 문제의 조건 대부분에 해결을 위한 실마리가 있었음

예) 상황정의 / 점화식도출 / 초기조건 / 최종목표

모두 손쉽게 구할 수있었음

 

- 어제의 방법을 연습한다고 별도의 리스트를 선언하는 방식으로 해결함

=> 하지만 공각복잡도도 고민해보면 좋음

 

- 지속적으로 실수하는것이 엣지케이스임 한번만 여부를 고민해보자!

=> n이 0, 1인경우에 대해서 놓침

 

<모범사례>

class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        
        t0, t1, t2 = 0, 1, 1
        for i in range(3, n + 1):
            t3 = t0 + t1 + t2
            t0, t1, t2 = t1, t2, t3
        
        return t2

-초기조건에 대해서 미리 정의해서 엣지케이스 고려

 

- 공간복잡도 O(1)을 고려한 방식!

 

- range(3, n + 1) 을 해서 최소화 가능!

 

<보충학습>

- DP 의 목적

=> 전반적으로 살펴보면 최적화가 주요 목적으로 판단됨

 

- 최적화 경우

비용은 최소화 / 이익은 최대화 / 자원 활용 최적화

 

 

• 비용 절감: 제한된 예산 내에서 최대한의 효과를 거두기 위해 최적의 자원 할당을 계산할 때.
• 성능 향상: 시스템의 성능을 최적화하기 위해, 최적의 경로를 찾거나 중복된 작업을 줄이는 경우.
• 자원 관리: 제한된 자원을 최대한 효율적으로 활용하기 위한 계획을 세울 때.
• 위험 최소화: 최악의 상황을 피하기 위해 최소한의 손실을 보장하는 전략을 수립할 때.