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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

코드

import sys

input = sys.stdin.readline

T = int(input())
lst = [0, 1, 2, 4] + ([0] * 7)

def caseNum(n):
    if n == 1:
        return lst[1]
    elif n == 2:
        return lst[2]
    elif n == 3:
        return lst[3]
    else:
        for i in range(4, n+1):
            lst[i] = lst[i-1]+lst[i-2]+lst[i-3]
    
    return lst[n]

for i in range(T):
    n = int(input())
    
    print(caseNum(n))

이 문제를 풀기 위해 우선 규칙성을 찾기 위해 직접 구해봤습니다.

1의 경우 (1개)
[1]

2의 경우 (2개)
[1+1][2]

3의 경우 (4개)
[1+1+1][1+2]
[2+1][3]

4의 경우 (7개)
[1+1+1+1][1+1+2]
[1+2+1][2+1+1]
[2+2][3+1]
[1+3]

5의 경우 (13개)
[1+1+1+1+1][1+1+1+2]
[1+1+2+1][1+2+1+1]
[2+1+1+1][1+1+3]
[1+3+1][3+1+1]
[1+2+2][2+1+2]
[2+2+1][2+3]
[3+2]

규칙
1 -> 2 -> 4 -> 7 -> 13
=> 1, 2, 3을 제외하고, 그 다음 수부터는 앞의 3가지의 수들의 합이랑 같다.

4의 경우는 7인데, 1, 2, 3의 경우를 더한 값과 같으며,
마찬가지로 5의 경우도 13인데, 2, 3, 4의 경우를 더한 값과 같습니다.

그래서 1,2,3의 경우를 고정으로 해놓고 그것보다 큰 수를 받았을 때, 앞의 3가지의 경우를 더한 값을 저장해서 반환했습니다.