백준 9095 1,2,3 더하기

1) 점화식
우선적으로 dp의 초기값을 지정해줘야 합니다.
dp[x]를 x를 만드는 경우의수라고 정의합니다.
dp[1] = (1) 이기에 1입니다.
dp[2] = (1 1 , 2)이기에 2입니다.
dp[3] = (1 1 1, 2 1, 1 2 , 3 )이기에 4입니다.
dp[1] = 1, dp[2] = 2, dp[3] = 4로 초기값을 지정해주었습니다.

dp[x] x >= 4부터는 점화식을 사용해야 합니다.
n의 범위가 11이라서 직접 구하는 미친 방법을 수행할수도 있겠으나..
지식인답게 문제를 해결하겠습니다.

4를 만드는 경우의수를 보면
1 1 1 1
2 1 1
1 2 1
1 1 2
1 3
3 1
2 2 총 7가지입니다.
그런데, 여기서 규칙성을 찾아보면

1 1 1 1 (1 + 3)
2 1 1 (2 + 2)
1 2 1 (1 + 3)
1 1 2 (1 + 3)
1 3 (1 + 3)
3 1 (3 + 1)
2 2 (2 + 2) 로 구성 되어 있습니다.
점화식의 정의 자체가 현재 x번째 상태를 이전 상태에 대해서 표현하는것이기에,
dp[x]를 q <= x - 1에 대해서 정의해야 합니다.
즉, dp[4] = dp[3](3을 만드는 경우) (앞에 1) + dp[2](2를 만드는 경우)(앞에 2) + dp[1](1을 만드는 경우)(앞에 3) 입니다.
즉, dp[x] = dp[x - 1] + dp[x- 2] + dp[x - 3]; 입니다.

2. Source Code

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mod 10000007
#define INF 100000000
#define pb push_back
#define pi 3.141592
using namespace std;

int dp[101010];
void clear(){
    for(int i = 0; i < 101010; i++){
        dp[i] = 0;
    }
}

int main(void){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int T;
    cin >>T;

    while(T--){
        int n;
        cin >> n;
        dp[1] = 1; //1
        dp[2]= 2; // 1 1 , 2
        dp[3] = 4; //1 1 1, 2 1 , 1 2 , 3
        for(int i = 4; i <= n;i ++){
            dp[i] = dp[i - 1] + dp[i-  2] + dp[i - 3];
        }
        cout << dp[n] << "\n";
    }

    return 0;
}