백준 알고리즘 - 피보나치 함수(1003번)[Python]

문제

 

문제 상황

- 재귀를 사용하여 해당 fibo를 호출할 때마다 카운팅을 하면 중복이 발생하여 연산이 너무 느리고 시간초과가 된다. 캐쉬를 사용하여 dp를 쓰면 counting을 할 수 없다.

 

해결 전략

- 0과 1을 분리하여 보면 이 사용 횟수도 부분적으로 피보나치를 따른다. 

코드 

t = int(input()) # testcase num
tc = [] # testcase 
for _ in range(t):
    tc.append(int(input()))
def fibo(n):        
    cache = [[0, 0] for _ in range(n+1)]
    if n == 0 :
        return [1, 0]
    cache[0] = [1, 0]
    cache[1] = [0, 1]
    for i in range(2, n+1):
        cache[i] = [cache[i-1][0] + cache[i-2][0],cache[i-1][1] + cache[i-2][1]] 
    return cache[n]
for i in range(t):
    tmp = fibo(tc[i])
    print(tmp[0], tmp[1])

해설

 

새로 학습한 것 & 실수

- [x + y for x, y in zip(first, second)] -> 길이가 같은 두 리스트에 같은 위치 값들의 합으로 새로운 리스트 생성

- fibo 정의에서 n이 0 일 경우 cache[1]값이 존재하지 않으므로 if구문으로 0 일때를 처리하지 않으면 out of index error가 발생한다. try except로 하지 않고 if 구문으로 return 처리하였다.