1, 2, 3 더하기

이 문제는 단순하다
숫자 N을 1, 2, 3의 숫자의 합을 이용해서 나타낼 수 있는 방법을 출력하면 된다.
해당 방식은 Bottom-Up 방식으로 점화식을 설계하는 것이 좋을 것 같다 생각했다.

다이나믹 프로그래밍에서는 dp배열에 대한 정의가 가장 중요하다.
내가 설정한 dp배열은 다음과 같다.

dp[i]: 숫자 i를 만드는 1, 2, 3의 조합 방식의 개수

dp[1]인 경우는 숫자 1을 만드는 1, 2, 3의 조합 방식의 개수다.
이 경우는 아래와 같다.

1
- 1

dp[1]은 1이다.

dp[2]인 경우는 숫자 2를 만드는 1, 2, 3의 조합 방식의 개수다.
이 경우는 아래와 같다.

2
- 1 + 1
- 2

dp[2]는 2이다.

dp[3]인 경우는 숫자 3을 만드는 1, 2, 3의 조합 방식의 개수다.
이 경우는 아래와 같다.

3
- 1 + 1 + 1
- 1 + 2
- 2 + 1
- 3

dp[3]은 3이다.

dp[4]인 경우는 숫자 4를 만드는 1, 2, 3의 조합 방식의 개수다.
이 경우는 아래와 같다.

4
- 1 + 3
- 1 + 1 + 2
- 2 + 2
- 1 + 1 + 1 + 1
- 1 + 2 + 1
- 2 + 1 + 1
- 3 + 1

dp[4]은 6이다.

위 4개의 dp배열 원소중 dp[4]를 보면 감을 잡을 수 있다.
dp[4]의 첫번째 방식인 '1+3'는 dp[1] 방식에 3을 더한 방식이고,
두번째 방식, 세번째 방식인 '1+1+2', '2+2'는 dp[2] 방식에 2를 더한 방식이고,
네번째, 다섯번째, 여섯번째 방식인 '1+2+1', '2+1+1', '3+1'은 dp[3] 방식에 1을 더한 방식이다.
그래서 점화식은 아래와 같이 나왔다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

그러므로 나는 소스코드를 다음과 같이 설계했다.

import sys

T = int(sys.stdin.readline().strip())

dp = [0 for _ in range(11)]
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 11):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
    # 각 dp배열 원소에서 1, 2, 3을 더하면 되는 원소의 개수 ex) dp[4]는 dp[3]에 1을 더한 개수,
    # dp[2]에 2를 더한 개수, dp[1]에 3을 더한 개수를 합치면 됨

for _ in range(T):
    n = int(sys.stdin.readline().strip())
    print(dp[n])