[백준][19단계 재귀] 10870번 /피보나치 수 5 (파이썬/Python)

1. 문제 설명

2. 코드

n = int(input())

if n == 0:
    print(0)
elif n == 1:
    print(1)
else:
    a,b = 0,1
    for _ in range(2,n+1):
        a,b = b,a+b
    print(b)

3. 풀이 과정

피보나치 수를 0,1인 경우를 빼고, 세 번째부터 진행하도록 for문을 만들면 된다.

피보나치 수는 점화식(recurrence relation)으로 정의되기 때문에

선형 동차 점화식 a,b = b,a+b로 계산해서 최종 b를 출력하면 된다.

4. 자투리 개념

• 점화식 (Recurrence Relation) : 재귀적 정의
  Fn​=Fn−1​+Fn−2​
• 선형 동차 점화식 (Linear Homogeneous Recurrence) : 상태 전이
  (Fn−1​,Fn​)→(Fn​,Fn+1​)