[백준/9095/파이썬] 1,2,3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

Problem

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

조건

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

SOL)

1,2,3의 숫자로 분해를 하나씩 해보면, F(N) = F(N-1)+F(N-2)+F(N-3)의 규칙을 알아내는건 어렵지않음!

이렇게, 뭔가 자연수를 분할하고, 특정 조건을 문제에서 제시할 때, 적어도 n=6~7 정도까지는 해보는 편이다. 

문제 이해 + 규칙성을 찾는다면, 완탐이 아니라, 수학적인 방법 or DP로 풀 수 있으니까.

하지만, 그 조건의 스케일이 클 때는, 나도 시뮬레이션을 많이 해보진 않음.(특히, 빡구현 문제는 시뮬레이션 한번 하는게 너무 오래걸림)

# Top -down
def sol(n):
    if n==1:
        return 1
    if n==2:
        return 2
    
    if n==3:
        return 4
    else:
        return sol(n-1)+sol(n-2)+sol(n-3)

tc=int(input())
for _ in range(tc):
    print(sol(int(input())))