[백준] 1003번 파이썬 (피보나치 함수)

1. 문제와 예제

(문제 링크: https://www.acmicpc.net/problem/1003)

1003번: 피보나치 함수

문제

예제

---

2. 전체 코드

1) 피보나치 함수 원리 그대로 적용 (시간 초과 오류 발생)

# 시간 초과
import sys
input = sys.stdin.readline

# 입력 받기
T = int(input().rstrip()) # 테스트 케이스 개수
dct = {}

# 피보나치 함수
def fibonacci(n):
    if (n == 0):
        dct[0] += 1
        return 0
    elif (n == 1):
        dct[1] += 1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

for _ in range(T):
    fibonacci(int(input().rstrip()))
    print(dct[0], dct[1]) # 결과 출력

처음 생각나는 방법은 문제에서 준 피보나치 함수를 이용해서 구현하는 것이지만 시간 초과 오류가 나는 것을 확인할 수 있다.

 

2) 다이나믹  프로그래밍

import sys
input = sys.stdin.readline

# 입력 받기
T = int(input().rstrip())
zero = [1, 0, 1] # 0의 개수 리스트
one = [0, 1, 1] # 1의 개수 리스트

for _ in range(T):
    N = int(input().rstrip()) # N번째 피보나치
    while (N >= len(zero)):
        zero.append(zero[-1] + zero[-2])
        one.append(one[-1] + one[-2])
    print(zero[N], one[N])

---

3. 코드 해설

시간 초과가 생기지 않도록 하려면 어떻게 해야할까 고민하는 과정에서 문제에서는 0과 1이 몇 번 출력되는지만 물어보는 것을 발견했다. 따라서 fibonacci(n)이 fibonacci(n-1)+fibonacci(n-2)로 쪼개진다는 점을 활용해 다이나믹 프로그래밍 방법을 이용했다.