[C#]피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• 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

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

 

내 풀이

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

느낀 점: 우선 피보나치 수에대해서는 잘 알고 있던 공식이라 어려움 없이 풀었다.

 

하지만 테스트 케이스 8번부터 통과되지 않았고, 공식에 틀린 부분이 없다는 것을 깨닫고 문제의 제한 사항을 확인해보았고,

 

자료형의 크기 때문에 테스트 케이스가 통과되고 있지 않았음을 알고,  모든 값을 int => long 형으로 바꾸려다가 문제에서 1234567로 나눈

 

나머지를 리턴하라는 문장을 확인하였고, 이 문제는 자료형  int형을 유지하면서 값을 도출하라는 것임을 알게되었다.

 

때문에  temp[i] 값을 temp[i-2]+temp[i-1] 에서 (temp[i-2]+temp[i-1])%1234567 로 수정해주니 모든 테스트 케이스가 통과되었다.