데구리 블로그

문제 링크 https://www.acmicpc.net/problem/1003 기본적인 피보나치 문제를 모르거나 시간초과가 문제라면 http://degurii.tistory.com/14?category=755814 를 참고하자. 기존의 피보나치 함수가 $$f(n) = f(n - 2) + f(n - 1)$$ 이므로 $n$일때 호출되는 0과 1의 개수를 $[$0의개수, 1의개수$]_n$ 로 표현해서 단순히 $[i, j]_n = [i, j]_{n - 2} + [i, j]_{n - 1}$ 처럼 쓸 수 있다. 이때, $[i, j] + [x, y] = [i + x, j + y]$로 정의한다. 정답 코드

문제 링크https://www.acmicpc.net/problem/2747 피보나치 수열은 보통 점화식으로 다음과 같이 표현된다. $$f(n) = f(n-2) + f(n-1), (f(0) = 0, f(1) = 1)$$ 이를 재귀함수로 구현하면 이렇게 되고, 위의 코드에서 $n = 6$인 경우 다음 그림처럼 함수가 전개된다. 재귀함수가 $n$을 인자로 호출되면 그 함수는 $n - 1$과 $n - 2$를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 된다. 결국 시간복잡도가 $O(2^N)$이므로 n 제한이 $n