[파이썬]백준 1003 피보나치

링크

백준 1003 피보나치

DP문제를 풀어본 경험이 적어서 해당 문제를 재귀를 사용한 DP로 풀었다.
memoization을 사용한다는 점만 기억나고 어떻게 접근해야 할지 감이 오지 않아서 다른 사람의 코드를 참고했다.
처음엔 다른사람의 코드를 보고도 흐름이 이해가 가지 않아서 직접 공책에 흐름을 그려보며 이해하려 노력했다.
DP도 많이 풀어보자

정답 코드

def fib(n):
    if n == 0 or n == 1:
        memo[n] = n
        return n
    elif memo[n] == 0:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

for _ in range(int(input())):

    memo = [0] * 41
    n = int(input())
    if n == 0:
        print('1 0')
    else:
        fib(n)
        print(memo[n-1], memo[n])

알게된 것👨‍💻

• 재귀는 정말 익숙해지지 않는다.
• memoizaion을 위한 리스트를 최대 크기만큼 미리 초기화 해놓는 것이 사용하기 편하더라..
• 재귀해서 나오는 결과값을 어딘가에 저장해놓고 그 값을 불러오면서 사용하면 되는데.. 더 연습해야할듯