[연습문제] 피보나치 수

출처: programmers.co.kr/learn/courses/30/lessons/12945

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

 

풀이과정

숫자의 범위가 크기 때문에 재귀로 구하면 시간 초과 에러의 위험이 있다.

---

풀이코드

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        if(n==1)
            return 1;
        // num1 : n-2
        // num2 : n-1
        // num3 : n
        int num1, num2, num3;
        num1 = 0;
        num2 = 1;
        num3 = num1 + num2;
        for (int i = 2; i < n; i++) {
            num1 = num2%1234567;
            num2 = num3%1234567;
            num3 = (num1 + num2)%1234567;
        }
        answer = num3;
        return answer;
    }
}

 

memo

다 구한 후에 마지막에 1234567로 나누려 했으나 테스트케이스7부터 통과되지 않는 어려움이 있었다.

피보나치 수가 커지면 int 자료형 저장 가능 범위를 벗어나는 이유 때문이였다.

 

그러던 와중에 질문하기에 누군가가 엄청난 꿀팁을 제공...

programmers.co.kr/questions/11991

프로그래머스

(A+B) % C 는 { (A%C) + (B%C) } %C 와 같다는 것이다.

모듈러 연산의 성질이라 하는데 처음알았다.