14495번/피보나치 비스무리한 수열/DP(동적계획법)

📕 문제

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

 

 

📗답안

 

def fibo(n):
    fibo_list = [0,1,1,1]

    if n > 3:
        for idx in range(4,n+1):
            fibo_list.append(fibo_list[idx-1]+fibo_list[idx-3])
        
    return fibo_list[n]

if __name__=="__main__":
    n = int(input())
    print(fibo(n))

📄 알고리즘 공부

 

f(n) = f(n-1) + f(n-3) 이니깐 리스트로 표현해서 계산하면 됨

수열 리스트 만들어서 (첫번째 인덱스는 0이니 두번째 인덱스부터)

입력받은 수 n을 fibo함수에 넣어서 값 리턴하기

 

 

 

☺️ 느낀점

DP 문제 더 풀어보고 익히기

이번 문제는 쉬운 버전인거 같다