백준(boj)15988 - 1,2,3더하기 3

문제 링크 - https://www.acmicpc.net/problem/15988

👀문제이해 및 풀이방법

역시 dp문제는 점화식 구하는게 너무 어렵다 그래도 차근차근 한번 생각을 해보면
1의답은 1 , 2의답은 2 , 3의답은 4, 4의답은 7 여기까지는 찬찬히 생각할 수가 있다
자 그럼 1 2 3 을 더하는 거니까 n의 답은 n-1의답들에 뒤에 +1만 해주면되고 n-2의 답들 뒤에 +2, n-3답들 뒤에 +3 해주면 되겠다
따라서 dp[n] = DP(n-1)+DP(n-2)+DP(n-3); 이렇게 해주면 되겠다✨

📝코드

#include <iostream>
#include <vector>
using namespace std;
int mod =1000000009;
class pus{
private:
    vector<int> dp;
    int size=1000000;
public:
    pus(){
        dp.resize(size+1,0);
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
    }
    int DP(int n){
        if(dp[n]!=0)
            return dp[n];
        dp[n]=((DP(n-1)+DP(n-2))%mod+DP(n-3))%mod;
        return dp[n];
    }
    void find_sol(){
        int a;
        std::cin >> a;
        std::cout << DP(a)<<'\n';
    }
};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    pus p;
    int n;
    std::cin >> n;
    for(int i=0;i<n;i++)
        p.find_sol();

    return 0;
}