[Programmers School] 피보나치 수

📆11/11
피보나치 수

<문제 설명>

<입출력 값>

<문제 해석>
자연수 n이 주어졌을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴해라.

<문제 해결>
피보나치 수열은 알고리즘 문제에서 많이 봐서 그런지 친근했다.
피보나치 수열을 배열에 넣어주고
for문을 돌려서 차례대로 값을 구해준다.
n번째 값을 구해주면 끝!

처음에는 a[n] % 1234567 만 해줬는데 몇개는 통과하고 몇개는 실패가 떴다.
이유를 찾다가 피보나치 수열 계산을 해줄 때 a[i]와 a[i+1]도 1234567로 나눈 값으로
바꿔줬더니 성공하였다.

**
78번째 이후부터는 표현은 되지만 '안전한 정수 계산'을 보장하지 못한다
따라서 (A+B)%C = ((A%C)+(B%C))%C 라는 수의 속성을 통해
F(n)%1234567 = ((F(n-1)%1234567)+(F(n-2)%1234567))%1234567 을 해줘야한다는 글을 참고하여 깨닫게 되었다.

<내 코드>

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int[] a = new int[n+1];
        a[0] = 0;
        a[1] = 1;
        for(int i=0;i<=n-2;i++){
            a[i+2] = (a[i]% 1234567) + (a[i+1] % 1234567);
        }
        answer = a[n] % 1234567;
        return answer;
    }
}```