1, 2, 3 더하기

출처 : 백준 #9095

시간 제한	메모리 제한
1초	512MB

---

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

---

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

---

입출력 예시

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

---

풀이

생각 및 풀이 설명

• 부분문제의 해를 통해 최적해를 구하는 다이나믹 프로그래밍 문제이다.
• basecase는 다음과 같다.
  • f(0) = 1
  • f(1) = 1
• 점화식은 다음과 같다.
  • if x ≥ 3
    • f(x) = f(x-1) + f(x-2) + f(x-3)
  • if x == 2
    • f(x) = f(x-1) + f(x-2)
  • if 1 ≥ x
    • f(x) = 1

python code

# 백준 9095번 1,2,3 더하기 (class3)
from sys import stdin
input = stdin.readline

def solution(n):
    arr = [1, 2, 3]
    temp = [0]*(n+1)
    # basecase 
    temp[0], temp[1] = 1, 1
    if n>=2:
        for i in range(2, n+1):
            for j in arr:
                if j <= i:
                    temp[i] += temp[i-j]
    return temp[n]

t = int(input())
result = []
for i in range(t):
    n = int(input())
    result.append(solution(n))

for j in range(t):
    print(result[j])