[알고리즘] 피보나치 수 2 - DP

문제 링크

 

피보나치 수 2 : https://www.acmicpc.net/problem/2748

 

문제탐색

기본 원리 탐색

• 피보나치 수열을 구현하는 문제입니다.
• 피보나치 수열은 n번째 항의 수 를 곧바로 구할수 없는 형태입니다.
• 그러므로 처음부터 n번째 까지 피보나치 수열의 규칙 (다음수 = 현재 수 + 이전 수) 에 따라 다음 피보나치 수를 계산해 나가면 됩니다. 

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• N  :  90
  • 다음 피보나치수를 구할땐  N-1 회 만큼 이전값+현재값을 해주면 되므로 =O(n) 시간복잡도에서 자유롭다고 볼수 있습니다.  
  • 단, 만약 90회 만큼 반복하였을때 변수가 받아들일수 없을만큼 큰 정수가 된다면 추가적인 방법을 생각해야 합니다. 우선 파이썬은 해당문제에서 자유롭기 때문에 그냥 구현하도록 합니다.

 

=> 반복문으로 동적 프로그래밍을 구현합니다.

 

 

코드설계하기

1. n을 입력받습니다.
2. 0과1이 들어있는 리스트를 선언합니다.
3. 두 숫자를 합한 값을 리스트에 추가하는것을 n-1회 수행합니다.
4. 리스트의 마지막 원소값을 출력합니다. 

 

시도회차 수정사항

 

정답코드

import sys
n=int(sys.stdin.readline())

fibonacci=[0,1] #0과1은 미리 생성
 
for x in range(n-1):# 1번쨰까지는 이미 있으므로 n-1회 수행합니다.
    fibonacci.append(fibonacci[x]+fibonacci[x+1]) # 다음수 = 현재수+이전수

print(fibonacci[-1])#마지막 원소 출력