[DP-1D][Easy] 1137.N-th Tribonacci Number

 

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

N-th Tribonacci Number - LeetCode

 

Q. Tribonacci를 주어진 n에 대해 다음과 같이 정의한다. 

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

이때 이 결과 값을 구하라.

 

 

Solution

 Dynamic Programming의 초석에 대당하는 문제. 

 피보나찌, triple 피보나찌, 원리는 같다. 

 이전 가까운 3개의 수의 합이 현재 수가 된다. 

 다만, 알고리즘으로 이 문제를 풀어낼때는, 약간이 최적화가 가미 되어야만 한다. 

 n까지 도달하기 위해서는 n까지 수를 전개 해야 하므로 O(n)의 TC가 필요하다. 

 n은 T(n-3)+T(n-2)+T(n-1) 이므로, 3배의 O(n)이 필요하게 된다. 

 이것은 바람직 하지 않으므로, 이럴때 보통 재계산 하는 과정을 피하기 위해 hash를 사용한다. 

 이를 통해 최종 TC 결과는 O(N)에 근접하게 된다. 

 

int tribonacci_help(map<int, int>& mapBuff, int n)
{
    map<int, int>::iterator itRet = mapBuff.find(n);
    if (itRet != mapBuff.end())
        return itRet->second;

    int nRet = tribonacci_help(mapBuff, n - 1) + tribonacci_help(mapBuff, n - 2) + tribonacci_help(mapBuff, n - 3);
    mapBuff[n] = nRet;
    return nRet;
}
int tribonacci(int n) 
{
    if (n == 0)	return 0;
    if (n <= 2) return 1;

    map<int, int> mapBuff;
    mapBuff[0] = 0;
    mapBuff[1] = 1;
    mapBuff[2] = 1;

    return tribonacci_help(mapBuff, n - 1) + tribonacci_help(mapBuff, n - 2) + tribonacci_help(mapBuff, n - 3);
}

 

 

결과.