[BOJ] 백준 1003 피보나치 함수 (Swift)

문제

https://www.acmicpc.net/problem/1003

풀이

시간제한이 0.25초로 짧은 편에 속하는 문제이다.

문제에서 주어진 대로 소스코드를 짠다면 시간복잡도는 $O(2^n)$이고, n이 최대 40이므로 0.25초 내에는 풀 수 없어 다른 방법으로 풀이해야한다.

f(2)를 구한다면 f(1), f(0)이 호출된다.
f(3)은 f(2) + f(1) 이므로, f(3) = f(1) + f(0) + f(1)이된다.
f(4)는 f(3) + f(2) 이므로 ...

f(0) = (0, 1), f(1) = (1, 0) 로 초기값을 설정하여, dp를 활용해서 풀 수 있을 것 같아서 풀이하였다.
$f(n) = f(n - 1) + f(n - 2)$
$f(0) = (0, 1), f(1) = (1, 0)$

이는 $O(n)$의 시간복잡도이며, 0.25초 내에 충분히 계산할 수 있다.

소스코드

후기

문제에서 주어진 대로는 풀 수 없고, 제한시간을 확인하여 다른 방법을 떠올려야 하는 문제