문제 정수 4는 1, 2, 3의 합으로 표현할 때 아래와 같이 7가지의 방법이있다.
1+1+1+1,
1+1+2,
1+2+1,
2+1+1,
2+2,
1+3,
3+1
자연수 N을 입력 받아, N 을 1, 2, 3의 합으로 표현할 때에,
몇 가지 방법이 있는지 계산하여 출력하는 프로그램을 작성하시오.
(우선은 오버플로우를 고려하지 않고 알고리듬을 기술할 것.)

입력
입력은 표준입력(standard input; 키보드를 통한 입력)을 사용한다.
입력은 첫 줄에 자연수 N이 하나 주어진다.
이때, N은 1이상 100000이하의 범위이다.

출력
출력은 표준출력(standard output; 모니터 화면에 출력)을 사용한다.
주어진 자연수 N을 1, 2, 3의 합으로 표현할 때에
가능한 방법의 수를 정수 형태로 출력한다.

def A(N):
    if N == 1:
        return 1
    elif N == 2:
        return 2
    elif N == 3:
        return 4
    else:
        return A(N-1)+A(N-2)+A(N-3)
N = int(input("경우의 수를 구하고 싶은 자연수 : "))
print(A(N))

풀이
변수 n을 표현 할 수 있는 경우의 수를 A(n)라 하면
N = 4
1 + 3을 표현 할 수 있는 경우의 수 = A(3)
2 + 2를 표현 할 수 있는 경우의 수 = A(2)
3 + 1을 표현 할 수 있는 경우의 수 = A(1)
A(1) = 1, A(2) = 2, A(3) = 4가 되며,
A(4) = A(3) + A(2) + A(1) = 4 + 2 + 1 = 7 입니다.
N = 5
1 + 4를 표현 할 수 있는 경우의 수 = A(4) = 7
2 + 3을 표현 할 수 있는 경우의 수 = A(3) = 4
3 + 2를 표현 할 수 있는 경우의 수 = A(2) = 2
A(5)는 A(4) + A(3) + A(2) A(1)=0 = 7+4+2 = 13 입니다.

해당 알고리즘의 점화식

요약

이전에 만든 수에서 1,2,3을 각각을 더했을 때 현재의 수가 나오므로
1을 더했을 때, 2를 더했을 때, 3을 더했을 때 현재의 수가 나오는 각각의 이전 조합의 경우의 수를 더하면 됩니다.
시간 복잡도 : $O(n)$