[BOJ] 1003. 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

풀이

• 메모이제이션 문제

• 0, 1의 개수 정보를 글로벌 변수로 선언해 입력값 들어왔을 때 기존에 계산한 정보 있으면 바로 리턴해줌.

• 그리고 계산정보 없을경우 이전 개수 정보를 기반으로 최소한의 계산만 수행해 시간을 단축

# global 변수로 0, 1 카운트 정보 놔둠
zero = [1, 0]
one = [0, 1]


def solution(n):
    # 입력값 n이 이전 정보에 있을 경우 -> 바로 값을 리턴함.(중복계산 방지)
    if n <= len(zero) - 1:
        print(f"{zero[n]} {one[n]}")
    
    else:
        # n이 len(zero)보다 크니까 n-len(zero)번만 계산해주면 됨
        for i in range(len(zero), n+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
        
        # 계산 다 끝나면 해당 정보를 리턴
        print(f"{zero[n]} {one[n]}")

n = int(input())
for _ in range(n):
    m = int(input())
    solution(m)