[프로그래머스] level2. 피보나치 수 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 피보나치 수 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

---

# 접근 방법 및 풀이 

 

• DP의 대표적인 문제인 피보나치 수를 풀어봤다. 메모이제이션을 이용해서 Fibo함수 재귀로 풀었는데 7번부터 쭉 실패가 떴다.
• ..? 로직에 뭐가 잘못되었나 했는데, 피보나치 수를 담는 배열의 자료형이 int였는데 44번째만 넘어가도 이미 int의 범위를 넘는다는 것이다. 
• 그래서 또 아무생각 없이 long으로 했는데 당연히 택도 없죠^^..
• 여기서 힌트는 피보나치 수를 1234567로 나눈 나머지 값이라는 것이다. 나머지 값이면 1234567을 넘지 않기 때문에 return 값인 int에도 잘 맞는 값이다.
• 모듈러 분배법칙을 잘 알고있다면 바로 풀 것이다. 근데 난 또 곱셈같은 분배 법칙인줄..^^
• ( A + B ) % C =  (( A % C + B % C )) % C
• 그럼 int 범위 안에 값이 잘 나온다! 
• 자세한건 코드참조

# 주의할 점 

 

• int범위 생각할것! 피보나치수 44번째만 넘어가도 int범위 넘어감

 

JAVA 코드

class Solution {
    public int solution(int n) {
        return Fibo(n);
    }
    static int memo[] = new int[100001];
    public static int Fibo(int n){
        if( n <= 1){
            return n;
        }
        if(memo[n] != 0)
            return memo[n];
        return memo[n] = (Fibo(n-1)%1234567 + Fibo(n-2)%1234567)%1234567;
    }
}

 

 

 

REVIEW