[백준,Python]1003번 피보나치 함수(DP,dynamic programming)

1003번 피보나치 함수(DP)문제 : https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

이 문제는 테스트 케이스 수를 받고, 피보나치 함수를 실행했을 때 Fib(0)과 FIb(1), 0과 1이 몇 번 호출되는지 출력하는 문제입니다.

일단, 다른 문제들에서는 그렇게 시간 제한에 대한 제약이 없었는데, 이번 문제에서는 확실히 0.25초(감이 잘 안잡히긴 하지만) 줄어들었습니다..

문제에서 요구하는 바가 확실히 , '이러이러한 식으로 풀면 컴파일 시간이 오래 걸리기에 풀지 마라'라고 정의 해 둔 것으로 느껴집니다.

일단 그런 것 상관없이 설마 시간이 넘겠어? 라는 마인드로 구현을 해보았습니다.

import sys
arr = [] # 함수를 돌릴 때마다 리스트를 초기화해 주고 append함.
def fibonacci(n):   
    if n==0:
        arr.append(0)
        return 0
    elif n==1:
        arr.append(1)
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)    
k= []
T = int(sys.stdin.readline())
for i in range(T):
    t = int(sys.stdin.readline())
    k.append(t)
for i in range(T):    
    fibonacci(k[i])
    print(str(arr.count(0))+' '+str(arr.count(1)))
    arr=[]

-역시나, '시간 초과'가 나타났습니다 :(

-그래도 input()이 시간을 많이 잡아먹으니까, 신경 써서 sys패키지에서 readline메소드를 이용했지만 그렇게 줄여도, 역부족이었던 것 같습니다..

 

그래서 무작정 규칙이 어떻게 되는 지 찾기 위해, n이 6일 때까지 모두 적어 보았습니다.

1.빨간색 규칙, 2.파란색 규칙

그림을 보면,1. 빨간색에서 1의 호출 수가 n+1의 0의 수인 규칙 2. 파란색에서 0의 호출 수와 1의 호출 수의 합이 n+1의 1의 호출 수라는 규칙 2가지를 찾을 수 있었습니다.

이 관계를 바탕으로 코드를 다시 구현하였습니다.

 

#테스트 케이스를 출력받고 0이 출력되는 횟수, 1이 출력되는 횟수를 공백으로 구분해서 출력.
import sys
n = int(sys.stdin.readline())
for i in range(n):
    t = int(sys.stdin.readline())  
    zero = 1
    one = 0
    temp = 0 # 초기화
    for _ in range(t):
        temp = one
        one += zero
        zero = temp
    print(str(zero)+' '+str(one))

-받은 수를 바로 포문 도려서 n+1 일 때, n의 one과 n의 zero를 더해준 값을 n+1의 oned으로 설정하였고, n의 one을 temp로 빼서 n+1의 zero로 넣어주었습니다.