백준 15990번 : 1,2,3 더하기 5 - DP

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

1.문제설명

이 문제에서는 덧셈을 할 때 숫자가 중복되면 안되므로

마지막으로 끝난 숫자가 중요하다.

즉 합의 상태를 저장하면서 동시에 마지막 숫자의 상태를 저장해줄 필요가 있다.

 

이를 점화식으로 나타내면

dp[합][마지막 숫자] = 합을 나타낼 수 있는 경우의 수

로 나타낼 수 있고

 

더해지는 숫자는 1, 2, 3이기 때문에

dp[i][3] = (dp[i-3][1] + dp[i-3][2]);
dp[i][2] = (dp[i-2][1] + dp[i-2][3]);
dp[i][1] = (dp[i-1][2] + dp[i-1][3]);

이렇게 나타낼 수 있다.

 

 

 

 

 

---

 

 

 

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;

long long dp[100001][4];

void calDP(){
    dp[1][1] = 1, dp[1][2] = 0, dp[1][3] = 0;
    dp[2][1] = 0, dp[2][2] = 1, dp[2][3] = 0;
    dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1;

    for(int i=4; i<=100000; i++){
        dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % mod;
        dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % mod;
        dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % mod;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    calDP();

    int t;
    cin >> t;
    for(int T=0; T<t; T++){
        int a;
        cin >> a;

        cout << (dp[a][1] + dp[a][2] + dp[a][3]) % mod << '\n';
    }



    return 0;
}