오늘의 알고리즘(5월 4일)

1. 백준, 피보나치 수, 2747번

www.acmicpc.net/problem/2747

2747번: 피보나치 수

---

2. 생각해보자

• 피보나치 수열에 대해 이해한다. 
• 피보나치는 0과 1로 시작한다. 0번째 수는 0, 1번째 수는 1이다. 그 다음, 2번째 수는 앞의 두 수의 합이 된다. 
• 피보나치 수열의 기본 공식을 이용한다. Fn = Fn-1 + Fn-2 (n ≥ 2)
• 첫번째 입력값 N은 45보다 작거나 같은 자연수다.

fibonacci = [0, 1]

n = int(input())

for i in range(2, n+1):
    fibonacci.append(fibonacci[i-1] + fibonacci[i-2])

print(fibonacci[-1])

---

3. 코드 해설 및 분석

n = int(input())

a, b = 0, 1

while n > 0:
    a, b = b, a + b
    n -= 1
    
print(a)