코드
def solution(n):
dp = [0 for _ in range(n+1)]
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n] % 1234567
이건 왜 레벨2 문제일까...?
재귀함수로도 풀 수 있고, DP로도 풀 수 있는 피보나치 문제이다. 그렇지만 재귀함수로 풀면 같은 연산을 여러번 반복한다는 매우 큰 단점이 있다. 시간복잡도가 O(2^n)으로 n이 커질수록 연산의 수가 급증한다. 그렇기 때문에 한 번 연산한 숫자는 저장해놓고 필요할 때 그 값을 가져다 쓰는 DP로 푸는 것이 효율적이다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 프로그래머스 멀리 뛰기 (0) | 2022.11.04 |
---|---|
[Python/파이썬] 프로그래머스 등굣길 (0) | 2022.10.26 |
[Python/파이썬] Summer/Winter Coding(~2018) 스티커 모으기(2) (0) | 2022.10.12 |
[Python/파이썬] 프로그래머스 정수 삼각형 (0) | 2022.10.10 |
[Python/파이썬] 백준 11049번 행렬 곱셈 순서 (1) | 2022.10.05 |