[백준] 1003번 피보나치 함수 _ 문제 풀이

1. 문제

https://www.acmicpc.net/problem/1003

2. 풀이

2.1. 오답 풀이

처음에는 단순하게 재귀함수를 사용하여 문제를 해결하여 시간초과가 발생했다.

d= [0, 0]
def fibo(depth):
    if depth == 0 or depth == 1:
        d[depth] += 1
        return
    fibo(depth-1)
    fibo(depth-2)

test_n = int(input())
for i in range(test_n):
    d = [0, 0]
    fibo(int(input()))
    print('%d %d' % (d[0], d[1]))

2.2. 정답 풀이

피보나치의 원리를 이용하여 이전 값을 이용하여 구해주어야 한다. 예를 들어, 입력 인자가 10인 경우에는 9와 8일 때 얻을 수 있는 0과 1의 값을 더한 값으로 갱신한다.

dp = [[1, 0], [0, 1]]
test_n = int(input())
for i in range(2, 40+1):
    dp.append([ x+y for x, y in zip(dp[i-1], dp[i-2]) ])

for t in range(test_n):
    now_depth = int(input())
    print(dp[now_depth][0], dp[now_depth][1])

PREVIOUS[프로그래머스] 정수 제곱근 판별 문제 풀이

NEXT[백준] 10773번 제로 _ 문제 풀이