Baekjoon 문제 풀기 (2748번 : 피보나치 수 2) Python

2748번 : 피보나치 수 2

1. 문제읽기

---

피보나치 수열을 찾는 문제

브론즈 2에 똑같은 문제가 있었는데 뭐가 다른지는 모르겠다.
아무튼 여러번 풀어보니까 조금 손에 익는 느낌이다.
이번에도 역시나 탑다운 방식부터 생각이 나서 조금 애를 먹었다.

2. 제출 코드

---

처음에 배열을 다 만들어놓고 시작하는 것이 아직 익숙하지 않아서 append를 썼다.
찾아보니 append의 시간 복잡도는 O(1)이라서 크게 다르진 않을 것 같다.

n = int(input())

arr = [0, 1]

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

print(arr[n])

3. 공부할 것

---

그래도 동빈북을 보면서 초기화 한 코드로 다시 수정해보았다.
n = 90 일때 시간을 측정해보았는데, 0.4초정도 아래 코드가 빨라서 신기했다.

n = int(input())

arr = [0] * 91

arr[0] = 0
arr[1] = 1

for i in range(2, n+1):
    arr[i] = (arr[i-1] + arr[i-2])

print(arr[n])