💡 DP란?
- 입력 크기가 작은 부분 문제들을 모두 해결하여 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘
- 재귀와 방식이 매우 유사하나 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있는 재귀의 문제를 해결하기 위해 DP를 사용한다.
=> 즉, 분할된 하위 문제가 동일한 반복이 일어나면 DP를 사용한다.
💡 DP의 구현 방식
- recursive 방식 ( 재귀 ) : fib1()
- iterative 방식 ( 반복 ) : fib2()
- memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 구현한 것이 성능면에서 효율적
재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문
T = int(input())
for test_case in range(1, T + 1):
N = int(input())
arr = [0] * (N + 1)
arr[10] = 1
arr[20] = 3
for i in range(30, N + 1, 10):
arr[i] = 2 * arr[i-20] + arr[i-10]
# print(arr)
print(f'#{test_case} {arr[N]}')