1137. N-th Tribonacci Number

(25.01.25)

문제이해

n을 넣었을 때 n번째 트라이보나치 수를 리턴해라

문제 접근

• 사실 첨에 피보나치인줄알고 했다가 이상함을 눈치챘다. 가장쉽게 반복문으로 구현해보자.

class Solution {
    public int tribonacci(int n) {
        int num1=0, num2=1, num3=1, tmp;
        if(n==0)
            return num1;
        else if(n==1)
            return num2;
        else if(n==2)
            return num3;

        for(int i=0; i<n; i++){
            tmp=num1+num2+num3;
            num1=num2;
            num2=num3;
            num3=tmp;
        }
        return num1;
    }
}

바로 통과하였다. 다만 재귀함수로 피보나치 접근하는게 가물가물하기에 이참에 위 코드를 재귀함수를 사용하는 방식으로 리팩터링 해보자.

놀랍게도 TLE가 발생하였다. 위 문제를 처음 보았을 때 피보나치처럼 정석인 재귀함수를 사용하는게 더 빠르겠지? 싶었는데 3번 호출로 인해 함수 콜 시간 탓인지 반복문이 훨씬 빠른 작동이 가능했다.