[2748] 피보나치 수 2(C#)

N번째 피보나치 수를 구하는 문제.

N은 자연수 90이하의 수로서

핵심은 피보나치 수를 계산할 때 자료형을 int가 아닌 long으로 받아야 한다는 것이다.

알고리즘 : Dynamic Programming
시간복잡도 : O(N)

int N = int.Parse(Console.ReadLine());

// N은 90이하의 자연수이다. 
// int형으로 받으면 범위초과로 제대로 된 답을 얻을 수 없다.
List<long> fibo2 = new List<long>();
fibo2.Add(0);
fibo2.Add(1);

for (int i = 2; i < N + 1; i++)
    if (fibo2.Count > 1)
        fibo2.Add(fibo2[i-1] + fibo2[i-2]);

Console.WriteLine(fibo2[N]);

 

 

다른 알고리즘에 대한 문제도 많이 접해봐야겠다.