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

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

16195번: 1, 2, 3 더하기 9

 

 

[난이도] Silver1
[유형] DP

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

주의할점 : tc 마다 계산하면 안되고 n=1000,m=1000 일때를 한번 계산해놓으면 모든 케이스를 구할 수 있으므로 재활용하면 된다.

 

 

#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);
        long long ans = 0;
        for(int i=0;i<=m;i++) ans=(ans+dp[n][i])%mod;
        printf("%lld\n",ans);
    }
} 

 

 

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