[1day 1sol]피보나치 함수

문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

구현

• 0의 개수: fib(n-1)의 값과 동일
• 1의 개수: fib(n)과 동일

 

코드

 

import sys
input = sys.stdin.readline


def fib(num, memo):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        if num not in memo:
            memo[num] = fib(num-1, memo) + fib(num-2, memo)
            return memo[num]
        else:
            return memo[num]


t = int(input())
for _ in range(t):
    n = int(input())
    dictionary = dict()
    if n == 0:
        print(1, fib(n, dictionary))
    else:
        print(fib(n-1, dictionary), fib(n, dictionary))

느낀점

dp 문제는 문제의 규칙을 이해하는 것이 정말 중요하다는 생각이 들었다. 그저 기능구현을 생각하다가 오래 걸릴뻔한 문제였다.