[백준] 1003번 : 피보나치 함수 (Python)

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

 

 

이 문제는 재귀함수로 피보나치 수열을 구할 때,
fibonacci(0), fibonacci(1)이 호출되는 개수를 구하는 문제다.

 

import sys

input = sys.stdin.readline

T = int(input()) # 테스트 케이스의 개수

answer = [0]*(41) # 정답 리스트
answer[0] = [1, 0]
answer[1] = [0, 1]

# 정답 리스트 생성
for i in range(2, 41):
    answer[i] = ([answer[i-1][1], sum(answer[i-1])]) # 다음 정답을 생성해 저장

# 문제 입력 & 정답 구하기
for _ in range(T):
    N = int(input()) # 값을 구할 N 입력받기
    print(*answer[N]) # 0과 1의 개수 print

 

 

[문제풀이]

---

 

간단하게 풀려면 재귀함수를 만들고 0, 1이 호출되는 개수를 count하면 된다.

그러나 이 문제의 시간 제한은 0.25초, 메모이제이션을 구현하는 등등의 방법을 써도 파이썬으로는

무조건 시간초과가 난다.

 

그러니 규칙을 찾아서 문제를 해결해야 한다.

 

 

 

 

 fibonacci(n)을 구할 때, 0의 개수와 1의 개수의 규칙은 이 2가지다.

 

이 규칙을 그대로 코드로 구현하면 끝!