[BOJ/백준][Silver1] 15992 : 1,2,3 더하기 7 (C++)

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

15992번: 1, 2, 3 더하기 7

 

 

[난이도] Silver1
[유형] DP

[풀이]
DP[N][M] : N을 M개의 수를 이용해 만들 수 있는 경우의 수.

 

#include <cstdio>
#include <cstring>
int t,n,m,dp[1001][1001],mod = 1e9+9;
int main(){
    scanf("%d",&t);
    dp[1][1]=dp[2][1]=dp[3][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            for(int k=1;k<4;k++){
                if(j-k>0) dp[j][i]+=dp[j-k][i-1];
                dp[j][i]%=mod;
            }
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
} 

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/15992.cpp