이친수

• 간단한 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)에 가능하다

"""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()

• Dependency: teflib.combinatorics.fibonacci