테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 이친수 ======

===== 풀이 =====
  * 간단한 DP 문제이다.
  * f[i]를 0으로 끝나는 길이 i짜리 이친수, g[i]를 1로 끝나는 길이 i짜리 이친수라고 하면 점화식은 아래처럼 나온다
    * f[i+1] = f[i]+g[i], g[i+1] = f[i]
  * g[i]를 f[i-1]로 치환하면 f[i+1] = f[i] + f[i-1]이니까 피보나치 수열 형태가 된다. 우리가 구하는 N자리 이친수는 f[N]+g[N]이니까 f[N+1]과 같다. 
  * n번째 피보나치 수를 구하는 것은 O(logn)에 가능하다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2193. 이친수".

- Problem link: https://www.acmicpc.net/problem/2193
- Solution link: http://www.teferi.net/ps/problems/boj/2193

Tags: [Fibonacci]
"""

from teflib import combinatorics


def main():
    N = int(input())
    print(combinatorics.fibonacci(N))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]]

{{tag>BOJ ps:problems:boj:실버_3}}