# 백준 1003 피보나치 함수
d = [0] * 10001
t = int(input())
for i in range(t):
d[0] = 1, 0
d[1] = 0, 1
n = int(input())
for i in range(2, n + 1):
d[i] = d[i-1][0] + d[i-2][0], d[i-1][1] + d[i-2][1]
print(d[n][0], d[n][1])
재귀 말고 반복문을 사용했다
문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보았다
0이 출력되는 횟수와 1이 출력되는 횟수를 튜플을 이용해 배열에 넣었다
보텀업 방식으로
f(3) = f(2) + f(1) = (f(1) + f(0)) + f(1) -> 트리로 그렸음
f(1)에는 0이 0번 1이 1번
f(0)에는 0이 1번 1이 0번
구하고 싶은 값이 d[3]라면?
d[0] = 1, 0
d[1] = 0, 1
d[2] = d[1] + d[1] = (0, 1) + (1, 0) = 1, 1
d[3] = d[2] + d[1] = (1, 1) + (0, 1) = 1, 2
이런식으로 출력되게 하였다
[파이썬] 백준 1931 회의실 배정 (0) | 2022.03.15 |
---|---|
[파이썬] 백준 2839 설탕 배달 (0) | 2022.03.08 |
[백준] 1926 그림 BFS (DFS는 참고만 하기 메모리 초과) (0) | 2022.02.13 |
[파이썬] 백준 1920: 수 찾기 (이진 탐색) (0) | 2021.08.28 |
[파이썬] 백준 2920: 음계 (구현) (0) | 2021.08.28 |