[Python] 백준 (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

---

풀이방법

• 점화식을 추론하자
  • 
    

    A1	A2	A3	A4
    1	1+ A(1)  -> (A1) = 1가지	1+(A2)  -> (A2) = 2가지	1+(A3)    ->(A3) = 4가지
    	2	2+(A1)  -> (A1) = 1가지	2+(A2)    ->(A2) = 2가지
    		3	3+(A1)    ->(A1) = 1가지
    1가지	2가지	4가지	7가지

  • 3을 만드는 방법은 1+1+1, 1+2, 2+1, 3 이렇게 4가지이다. 
  • 처음에 1이 들어왔을때 구할 수 있는 방법 2가지이고,  2가 들어왔을때 구할 수 있는 방법 1가지, 3이 들어왔을 때 구할 수 있는 방법 1가지
  • DP(N) = DP(N-1)+DP(N-2)+DP(N-3) 이 만들어진다.

import sys

T = int(sys.stdin.readline().rstrip())
answer = []

for i in range(T):
    A = [1, 2, 4]
    n = int(sys.stdin.readline().rstrip())
    if n >= 3:
        for j in range(3, n):
            A.append(A[j-3]+A[j-2]+A[j-1])
        answer.append(A[-1])
    else:
        answer.append(A[n-1])

for i in answer:
    print(i)