[프로그래머스]Lv.2 피보나치 수 C#(재귀)

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

프로그래머스

소스코드1( 재귀 사용 시간복잡도 오류)

public class Solution {
    public int solution(int n) {
           return fibonacci(n);
        }

         int fibonacci(int n)
        {
            if (n <= 1)
                return n;
            else
                return (fibonacci(n - 1) + fibonacci(n - 2)) % 1234567;
        }
}

소스코드2

public class Solution
{
    public int solution(int n)
    {
        int[] fibonArr = new int[n + 1];
        fibonArr[0] = 0;
        fibonArr[1] = 1;

        for (int i = 2; i <= n; i++)
        {
            fibonArr[i] = (fibonArr[i - 2] + fibonArr[i - 1]) % 1234567;
        }
        return fibonArr[n];
    }
}