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

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

def plus(x):
    if x == 1:
        return 1
    elif x == 2:
        return 2
    elif x == 3:
        return 4

    return plus(x - 1) + plus(x - 2) + plus(x - 3)


T = int(input())

for i in range(T):

    N = int(input())

    print(plus(N))

1,2,3까진 직접 경우의 수를 구한다.

4부터는 나눠서 생각했다.

3을 만드는 방법에 1을 더해주면 4가 된다.
마찬가지로 2를 만드는 방법에 2를 더해주면 4가 되고 1을 만드는 방법에 3을 더해주면 4가 된다.

즉, N을 만드는 수 = N-1 + N-2 + N-3이다