[BOJ] 9095 1,2,3 더하기 (Python3)

문제

정수 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   

문제풀이

아 진짜 다이나믹 프로그래밍 너무 싫다. 이건 코딩이 아니라 수학문제 아니냐고…
수학적으로 점화식을 찾아야 한다는 생각으로 풀어야겠다. 아니면 다시 고딩때 배운 수열 점화식부분이라도 다시 봐야하나…

이 문제는 경우의 수를 쭉 숫자순서대로 쓰다보면 규칙이 나오는 걸 알 수 있다.

1의 경우 1개
2의 경우 2개
3의 경우 4개
4의 경우 7개
5의 경우 13개

자세히 보다보면, 5의 경우는 2,3,4를 더한 값, 4의 경우는 1,2,3을 더한순으로, 직전 세번째 숫자까지의 경우의 수를 더하면 해당 숫자의 경우의 수가 나온다.

코드

from itertools import permutations
            
result = []
T = int(input())

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return solution(n-1) + solution(n-2) + solution(n-3)
    
for i in range(T):
    n = int(input())
    print(solution(n))
    
    

1
4
7