백준 2668번 - 줄어들지 않아

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

n번째 자리에서 끝자리에 있는 숫자에 따라 값을 저장해주면 되는 문제이다.

예를들어

n이 2일때 끝의 자리가 1인 경우의 수는 n이 1일때 끝의 자리가 0과 1일때의 경우와 같다.

n이 2일때 끝의 자리가 9인 경우의 수는 n이 1일때 끝의 자리가 0부터 9까지의 경우와 같다.

즉 다음과 같은 점화식을 세울 수 있다.

dp[n][j] = dp[n-1][0]+...+dp[n-1][j]

(n자리에서 끝이 j일때 경우의 수)

주의할 점은 자료형을 int로 하면 값의 범위에 벗어나기 때문에

long으로 정답을 출력해주면 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    
    int T;
    cin>>T;
    
    int n;
    for(int testCase=0;testCase<T;testCase++){
        scanf("%d",&n);
        
        long ans=0;
        vector<vector<long>> dp(n+1,vector<long> (10,0));
        for(int k=0;k<10;k++)
            dp[1][k]=1;
        
        for(int i=2;i<=n;i++)
            for(int j=0;j<10;j++)
                for(int k=0;k<=j;k++)
                    dp[i][j]+=dp[i-1][k];
        
        for(int k=0;k<10;k++)
            ans+=dp[n][k];
        
        printf("%ld\n",ans);
        
    }
    return 0;
}