[Python] 백준 풀기 2748 - 피보나치 수 2

파이썬 백준 2748번

브론즈 1

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

2748번: 피보나치 수 2

 

 

 

 

 

문제 보기

분류: 수학, 다이나믹 프로그래밍

 

 

 

 

 

문제 풀기

n 번째 피보나치 수를 저장하기 위해 n + 1 개의 빈 리스트를 준비한다.

리스트 첫번째와 두 번째 값은 0 과 1 로 초기화한다.

index 가 3 인 세번째 피보나치 수는 문제에서 제시한 함수를 따르기 때문에 아래 코드와 같이 작성되었다.

        num_ls[i] = num_ls[i - 1] + num_ls[i - 2]

이 코드를 2 부터 n 까지 for loop 를 돌려 다이나믹 프로그램 형식으로 모두 구한다.

저장된 리스트에서 구하고자 하는 n 번째 피보나치 수인 index n 의 값 출력.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnFibonacci(n):
    num_ls = [0] * (n + 1)
    num_ls[0] = 0
    num_ls[1] = 1
    
    for i in range(2, n + 1):
        num_ls[i] = num_ls[i - 1] + num_ls[i - 2]
    
    print(num_ls)           # test print
    print(num_ls[n])
    

if __name__ == "__main__":
    n = int(inputdata().strip())
    
    fnFibonacci(n)



# 10

# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

# 55