[백준] 2748번 피보나치2
'''2021.08.30 풀이
백준 2748 피보나치2
중복없애기 -> 다이나믹 프로그래밍 DP
동적 프로그래밍 : 저장소를 두고 나온 결과는 임시저장하고 다시 계산하지 않는 것
풀이 : 저장소 cache를 두고 푼다. (topdown 방식, bottomup 방식)
'''
# topdown 방식
def fib(cache, n):
if cache[n] != -1: #비어 있는지 확인
return cache[n]
if n == 0:
cache[n] = 0
elif n == 1:
cache[n] = 1
else:
cache[n] = fib(cache, n-1) + fib(cache, n-2)
return cache[n]
def solve():
n = int(input())
cache = [-1 for _ in range(n+1)] #초기화
print(fib(cache, n))
solve()
------------------------------------------------------------
# bottomup 방식 : 밑부터 하나씩 채워 넣는다.
def solve():
n = int(input())
arr = [0, 1] #초기화
for i in range(2, n+1):
value = arr[i-1] + arr[i-2]
arr.append(value)
print(arr[n])
solve()
Author And Source
이 문제에 관하여([백준] 2748번 피보나치2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choi46910/백준-문제풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)