[ BOJ / Python ] 10826번 피보나치 수 4
2540 단어 dynamic programmingDPpythonbojDP
이번 문제는 다이나믹 프로그래밍을 활용하여 해결하였다. 피보나치 수 문제는 워낙 많이 접해봐서 바로 풀 수 있었다. 메모라이제이션을 이용하여 연산의 크기를 줄였다.
점화식은 dp[n]=dp[n-1]+dp[n-2]를 사용하였다.
- n을 입력받는다.
- dp 배열을 [0, 1, 1] 뒤에 0 n개로 채운다.
- 3부터 n까지 반복하는 i에 대한 for문을 돌린다.
-> dp[i]를 dp[i-1]+dp[i-2]로 갱신한다. - dp[n]을 출력한다.
Code
n=int(input())
dp=[0]+[1]*2+[0]*(n)
for i in range(3, n+1):
dp[i]=dp[i-1]+dp[i-2]
print(dp[n])
n=int(input())
dp=[0]+[1]*2+[0]*(n)
for i in range(3, n+1):
dp[i]=dp[i-1]+dp[i-2]
print(dp[n])
Author And Source
이 문제에 관하여([ BOJ / Python ] 10826번 피보나치 수 4), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-10826번-피보나치-수-4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
