설명
1) DP 테이블 정의
d[i] = N
- 정수 i를 1, 2, 3의 합으로 나타내는 경우의 수
2) 점화식 찾기 (1부터 채워나감)
1. d[1] - 1가지
- 1
2. d[2] - 2가지
- 1 + 1
- 2
3. d[3] - 4가지
- 1 + 1 + 1
- 1 + 2
- 2 + 1
- 3
4. d[4] - 7가지
3) 점화식 작성
d[i] = d[i-1] + d[i-2] + d[i-3]
코드
1. Top-down 풀이방식 (재귀)
- Top-down은 Bottom-up보다 성능은 좋지 않지만 메모리와 가독성에 이점이 있습니다.
import sys
input = sys.stdin.readline
nums = [int(input().rstrip()) for _ in range(int(input().rstrip()))]
def logic(x):
if x == 1:
return 1
elif x == 2:
return 2
elif x == 3:
return 4
else:
return logic(x - 1) + logic(x - 2) + logic(x - 3)
for n in nums:
print(logic(n))
2. Bottom-up 풀이방식 (반복문 채우기)
- 메모리를 조금 더 필요로 하는 대신, Top-down에 비해 성능이 좋습니다.
import sys
input = sys.stdin.readline
nums = [int(input().rstrip()) for _ in range(int(input().rstrip()))]
d = [0] * (max(nums) + 2)
d[1] = 1
d[2] = 2
d[3] = 4
for i in range(4, max(nums)+1):
d[i] = d[i-1] + d[i-2] + d[i-3]
for n in nums:
print(d[n])
'알고리즘' 카테고리의 다른 글
[백준] 1182번 - 부분수열의 합 (Python) (0) | 2022.10.04 |
---|