[Java] 피보나치 수 - Bottom-Up/Top-Down (Lv. 2)

피보나치 수 - Bottom-Up/Top-Down (Lv. 2)

---

1. 문제

2. 풀이

---

1. 문제

프로그래머스

 

2. 풀이

- Bottom-Up

class Solution {
    public int solution(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        
        int[] fib = new int[n + 1];
        fib[1] = 1;
        fib[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        
        return fib[n];
    }
}

 

반복문을 사용하고 작은 문제를 해결하여 큰 문제를 해결하는 방식으로, 테이블을 채워가며 문제를 해결합니다.

 

- Top-Down

class Solution {
    private int[] fib = new int[100001];
    
    public int solution(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        
        if (fib[n] != 0) {
            return fib[n];
        }
        
        fib[n] = (solution(n - 1) + solution(n - 2)) % 1234567;
        return fib[n];
    }
}

 

메모이제이션으로 중복 계산을 방지합니다.

 

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3