[백준] 9095 1,2,3 더하기 C++ (DP)

백준 9095 1,2,3 더하기
https://www.acmicpc.net/problem/9095

---

---

입력받는 숫자를 1,2,3의 합으로 구성된 식의 개수를 구하는 문제이다.
예시를 보니 1+2, 2+1 는 서로 다른 식으로 보았다.
몇 가지는 직접 구해보았다.

n=1일 때 : 1

• 1

n = 2일 때 : 2

• 2
• 1+1

n=3일 때 : 4

• 3
• 1+2
• 2+1
• 1+1+1

n=4일 때 : 7

• 1+1+1+1
• 2+1+1
• 1+2+1
• 1+1+2
• 2+2
• 1+3
• 3+1

n=5일 때 : 13

• 1+1+1+1
• 1+1+1+2 => 4개
• 1+1+3 => 3개
• 2+2+1 => 3개
• 3+2
• 2+3

표로 정리해보았다.

입력 수 n	1	2	3	4	5	...
방법 수	1	2	4	7	13	...

규칙을 찾아서 점화식을 만들어 보자.
d[1] = 1
d[2] = 2
d[3] = 4
는 기본적인 값으로 고정해뒀다고 치면
n=4부터 시작된다.
d[4] = 4+2+1 = 7 이고
d[5] = 7+4+2 = 13 이다.
뭔가 수상하다
d[n] = d[n-1]+d[n-2]+d[n-3]의 규칙을 갖는다.
점화식 완성이다

이제 이 점화식을 n=4에서 n<11 동안 돌아가면 된다.

d[n] = d[n-1]+d[n-2]+d[n-3]

---

#include<iostream>
using namespace std;

int main()
{
    int T;
    int n;
    int dp[1001];

    scanf("%d",&T);

    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int j=4; j<11; j++) dp[j] = dp[j-1] + dp[j-2] + dp[j-3];

    for(int i=0; i<T; i++)
    {
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
}