[DP] 세보나치 수열

DP:  dynamic programming

미리 준비한 테이블을 통해 가장 작은 부분 문제를 먼저 풀고, 이미 해결한 부분 문제를 통해 상위 부분 문제를 풀어나가는 방식

 

세보나치 수열이란? F(1) = 1, F(2) = 2, F(3) = 3

F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3

 

세보나치 수열은 다음과 같이 재귀적으로 정의한 수열이다.
F(1) = 1, F(2) = 2, F(3) = 3
F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3

양의 정수 n이 주어졌을 때, n번째 세보나치 수열 F(n)을 출력하시오.

Input
첫째 줄에 양의 정수 n이 주어진다. 1<= n <= 100,000
4

6

100

Output
첫째 줄에 세보나치 수열의 n번째 항 F(n)을 출력한다.
6

230

151404293106684183601223222

# dp로 문제 해결 & 공간 복잡도 문제 해결
import sys
input=sys.stdin.readline

def sebo(n):
    if n<4:
        return n
    else:
         a, b, c = 1, 2, 3
         for _ in range(4,n+1):
            a, b, c = b, c, a+b+c
    return c

n=int(input())
print(sebo(n))