모든 챌린지
쉬움 0명 해결 정답률 0%

트리보나치 수

각 항이 앞의 세 항의 합인 트리보나치 수열의 n번째 항을 반환합니다.

배우게 될 내용

  • 수열을 반복문으로 계산할 수 있다
  • 마지막 몇 항만 유지할 수 있다
  • 처음 몇 항을 직접 처리할 수 있다

문제

원문 보기 (영어)

트리보나치 수열은 피보나치 수열의 아이디어를 세 항으로 넓힌 것입니다. 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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.