[ 99클럽/미들러 ] 2일차 TIL : 피보나치 수

---

문제 요약

피보나치 수란, F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수를 말한다.
2이상의 n이 입력될 때, n번째 피보나치 수를 1234567로 나눈 나머지를 반환하라

[ 예시 ]

n	return
3	2
5	5

[ 제약 조건 ]

• $2<= n <= 100,000$

[ 프로그래머스 ]

• Java
• 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12945

---

풀이

• DP의 하향식으로 구현

1) 이전 값을 활용할 수 있도록 memorization 배열을 선언한다.
2) n 값이 1 또는 2인 경우, 0을 반환한다.
3) 그 이상의 값일 경우, 해당 n 번째에 기억된 값을 반환한다.
4) 합동식에 의거하여 $(A+B)\ \%\ C$ 형태로 식을 구성한다.

---

Code

import java.util.*;
class Solution {
    static int[] dp;
    
    private static int fibo(int n){
        if (n==1 || n==2) return 1;
        if (dp[n] != 0) return dp[n];
        dp[n] = (fibo(n-1) + fibo(n-2))%1234567;
        
        return dp[n];
    }
    
    public int solution(int n) {
        dp = new int[n+1];
        int answer = fibo(n);
        return answer;
    }
}

---

시도

1) 재귀함수

처음엔 재귀함수만을 사용하여, 문제를 푸고자 했다. 다만, 입력값 n이 10만 이하이기 때문에 시간 초과가 발생한다.

2) DP

이전 계산값을 사용하여 계산 횟수를 획기적으로 줄이는 DP의 하향식을 사용하여 코드를 작성했다. 하지만, int의 범위인 214,7483,647을 넘게 되면서 이상한 값이 계산되게 된다.

3) BigInteger

그렇다면, int보다 범위가 큰 BigInteger를 사용하면 어떨까?라는 생각으로 구현하였으나 편법일 뿐 문제가 원하는 의도된 풀이가 아닌 거 같았다.

4) 합동식

합동식에는 재밌는 성질이 많다. 이 문제에선
$(A+B)\ \%\ C≡ (A\ \%\ C) + (B\ \%\ C) \ \% C$
이라는 성질을 사용하였고, 이로 인해 각 재귀함수마다 %1234567의 값이 계산되며, int에서도 오버플로우를 발생시키지 않는다.

느낀점

DP를 아는 개념이었기 첫 번째 시도 이후 바로 생각났지만, 오버플로우에서 문제가 생길 줄 몰랐다. 문제의 의도를 파악하는 것이 중요함을 다시 한 번 느꼈다.