[백준] 9095번 - 1, 2, 3 더하기 (Python)

설명

---

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])