[99클럽 코테 스터디] 41일차 TIL DP

 

 

오늘의 문제는 LeetCode

 

1137. N-th Tribonacci Number

 

 

문제

 

 

문제 설명 

정수 n이 주어졌을 때 Tn의 Tribonacci 수열을 구하는 문제입니다. Tn은 다음과 같이 정의됩니다. 

T0 = 0, T1 = 1, T2 = 1 

Tn+3 = Tn + Tn+1 + Tn+2

 

[입력 예시]

n = 4

[출력 예시]

4

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 36분이 걸렸습니다.

 

 

 

문제 접근 방식

우선 n이 0, 1, 2일 땐 주어진 값이 있으므로 조건문을 통해 해당 값을 반환해줍니다. 

다음으로 배열을 생성해 초기 인덱스에 대한 Tribonacci 수열의 값을 할당합니다. 세번째 인덱스부턴 반복문을 사용해서 주어진 수식에 따라 값을 계산하고 n 번째 Tribonacci 수열의 값을 반환합니다. 

 

 

 

문제 풀이

class Solution {
    public int tribonacci(int n) {
        
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }

        int[] dp = new int[n + 1]; 

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        return dp[n]; 

    }
}

 

 

 

첫 번째 시도 

첫 번째 시도에서는 재귀 호출을 사용해 문제를 해결하고자 했습니다. 그런데 제출 했을 때 Time Limit Exceeded 오류가 발생했습니다. 이는 동일한 입력에 대해 너무 많은 재귀 호출이 발생하여 생긴 문제입니다. 이러한 문제를 해결할 때 계속해서 재귀적으로 접근하는 습관이 있는데 이번 경험을 통해 메모리 관리 및 시간 복잡도를 고려한 다른 접근 방식의 필요성을 느꼈습니다. 

class Solution {
    public int tribonacci(int n) {

        int answer = cal(n); 
        return answer; 
    }

    public static int cal(int num) {
        int t = num - 3; 
        
        if(num < 3) {
            switch(num) {
            case 0 : 
            return 0;
            case 1 :
            return 1;
            case 2 :
            return 1; 
            }
        }

        return cal(t) + cal(t+1) + cal(t+2);

    }
}

 

 

 

 

메모이제이션 사용하기 

메모이제이션은 계산된 결과를 저장해서 동일한 계산을 반복하지 않도록 하는 기법입니다.

배열을 생성하여 각 Tribonacci  수를 계산할 때마다 해당 값을 배열에 저장합니다. dp[i]는 이전 세 개의 값만을 사용해 계산 하기 때문에 반복적인 계산을 피할 수 있습니다. 

 

 

 

주어진 수식 변형하기 

문제에서 주어진 식은 Tn+3 = Tn + Tn+1 + Tn+2입니다. 이는 n+3 번째 수는 n 번째 수와 n+1 번째수 그리고 n+2번째 수를 전부 더한 값이라는 것입니다. 

이 공식을 배열을 통해 표현해보면 dp[i]가 Ti를 저장한다고 볼 수 있습니다. 따라서 dp[n]은 Tn을, dp[n+1]은 Tn+1을, dp[n+2]는 Tn+2를 뜻합니다. 이 때, Tn+3을 배열 인덱스로 표현하면 dp[n+3]이 됩니다. 주어진 식을 이에 맞게 배열 인덱스로 변환하면 dp[n+3] = dp[n] + dp[n+1] + dp[n+2]가 됩니다. 

이 공식을 일반화 하면, n+3을 i로 치환할 수 있습니다. 즉 아래와 같은 식이 성립되게 됩니다. 

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

 

 

 

 

 

 

이렇게 오늘 41일차 TIL을 작성해 보았습니다.