(파이썬)백준 알고리즘 1003번 피보나치 함수

백준 알고리즘 저지 1003번 문제 (https://www.acmicpc.net/problem/1003)

보통 피보나치의 문제와 다른점은 분할 과정에서 func(0)과 func(1)이 몇번 호출되는지를 결과로 보여줘야 한다는점.

마땅한 대책을 생각 못해서 n을 1씩 증가시키며 몇번의 0과 1이 호출되는지를 분석해보니 초기 몇가지 값 빼고는 피보나치 수열처럼 n0 = n-1 + n-2의 규칙을 띄고 있는 것을 알게됐음

이를 이용하여 함수를 만들었는데 시간초과로 통과하지 못했음.

n이 40인 경우가 T번 입력되는 최악의 경우에 매번 연산을 해야했기 때문.

그래서 c0, c1이라는 배열을 만들어서 이미 계산된 n까지의 경우를 저장하도록 해서 반복연산을 줄임.

 
c0=[1,0,1]
c1=[0,1,1]

def fibo(n):#6
    l=len(c0)#3
    if l<=n:
        for i in range(l,n+1):
            c0.append(c0[i-1]+c0[i-2])
            c1.append(c1[i-1]+c1[i-2])
    print('%d %d'%(c0[n],c1[n]))
for _ in range(int(input())):
    fibo(int(input()))

나도 길을 헤메일 누군가를 위해 코드를 공유하지만 이 글을 보고 있다면 문제 해결방법을 충분히 고민한 뒤에 찾아보는 것이길 바람

(추가적으로 알고리즘은 현답은 있지만 정답이 없는 문제라고 생각함.. 더 나은 풀이법이 있다면 다같이 공유할 수 있었으면 좋겠음!)