1,2,3 더하기

문제
정수 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의 합으로 나타내는 방법의 수를 출력한다.

입력	출력
3	7
4	44
7	274
10

Solution

import sys
input = sys.stdin.readline

# 테스트 케이스 수 입력 받기
t = int(input())

# dp 진행
def solution(n):
  # 1 -> 1 => 1개 
  if n == 1:
    return 1
  # 2 -> 1+1, 2 => 2개
  elif n == 2:
    return 2
  # 3 -> 1+1+1,1+2,2+1,3 => 4개
  elif n == 3:
    return 4
  else:
    return solution(n-1)+solution(n-2)+solution(n-3)

# 테스트 케이스 수 만큼 정수 입력받아서 dp
for i in range(t):
  n = int(input())
  print(solution(n))

1. 1 => 1개
2. 1+1, 2 => 2개
3. 1+1+1,1+2,2+1,3 => 4개
4. 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1 => 7개
   • 1, 2, 3의 경우의 수를 합한 것과 같음
5. 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+1+3, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2,2+2+1, 1+3+1, 3+1+1, 2+3, 3+2, => 13개
   • 2,3,4의 경우의 수를 합한 것과 같음

점화식

(n>3)일 때, f(n) = f(n-1)+f(n-2)+f(n-3)

Ref :
https://yongku.tistory.com/1273