[프로그래머스 : Java] 피보나치 수 (피보나치 수열의 규칙)

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

1. 풀이 및 피보나치 수열의 규칙

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (단, n은 2 이상인 자연수)

피보나치 수열은 위의 규칙에 따라 시작 값인 0과 1부터 시작하여, 이전 두 개의 값을 더해서 다음 값을 생성하는 수열입니다. 수열은 무한히 이어지며, 각 항은 이전 두 항의 합으로 계산됩니다.

피보나치 수열의 처음 몇 항은 다음과 같습니다:
F(0) = 0 

F(1) = 1 

F(2) = F(0) + F(1) = 0 + 1 = 1 

F(3) = F(1) + F(2) = 1 + 1 = 2 

F(4) = F(2) + F(3) = 1 + 2 = 3 

F(5) = F(3) + F(4) = 2 + 3 = 5 

F(6) = F(4) + F(5) = 3 + 5 = 8 ...

이렇게 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...와 같이 이어집니다.

2. 코드

class Solution {
    public int solution(int n) {
         int[] fb = new int[n + 1]; // 피보나치 수 담을 배열 초기화
        //F(0) 과 F(1) 은 0과 1로 고정의 값임
        fb[0] = 0;
        fb[1] = 1;

        for (int i = 2; i <= n; i++) {
            // 두 수의 합을 1234567로 나눈 나머지를 현재 수로 저장
            fb[i] = (fb[i - 1] + fb[i - 2]) % 1234567; 
        }

        return fb[n];
    }
}