문제
트리보나치 수열은 피보나치 수열의 아이디어를 세 항으로 넓힌 것입니다. T(0) = 0, T(1) = 0, T(2) = 1이고, 그 뒤로는 T(n) = T(n − 1) + T(n − 2) + T(n − 3)입니다. 수열은 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, … 로 이어집니다.
tribonacci(n) 함수를 구현하세요.
입력
n: 항의 인덱스이며 0부터 셉니다.
출력
T(n)을 반환합니다. 언제나 마지막 세 항만 있으면 되므로 변수 세 개를 쓰는 반복문으로 충분합니다.
제약 조건
0 ≤ n ≤ 74
예시
예시 1
입력:
n = 7
예상 출력:
expected = 13
입력:
long long n = 7;
예상 출력:
long long expected = 13;
입력:
long n = 7;
예상 출력:
long expected = 13;
설명
항은 0, 0, 1, 1, 2, 4, 7, 13이므로 T(7) = 13입니다.
예시 2
입력:
n = 2
예상 출력:
expected = 1
입력:
long long n = 2;
예상 출력:
long long expected = 1;
입력:
long n = 2;
예상 출력:
long expected = 1;
설명
T(2)는 수열에서 처음 나오는 1이므로 1입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
처음 세 항은 바로 반환하세요.
힌트 2
변수 세 개를 두고 단계마다 한 칸씩 밀어 주세요.
힌트 3
메모이제이션 없는 재귀는 같은 계산을 반복해서 너무 느립니다.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.