99클럽 코테 스터디 2일차 TIL + DP

문제

Baekjoon14495: 피보나치 비스무리한 수열

• 설명: n이 주어졌을 때 f[n -1] + f[n - 3]을 구하여 준다

풀이

• 재귀로 주어진대로 구현하면 시간초과가 날 수 있으므로 DP를 사용하여 구해준다

오늘의 회고

• 가장 기본적인 DP 문제. 좀 더 어려운 DP도 풀어보자

Code

n = int(input())

f = [0] * 200
f[1] = f[2] = f[3] = 1
for i in range(4, n + 1):
    f[i] = f[i - 1] + f[i - 3]
print(f[n])