[백준 2688] 줄어들지 않아 (C++)

문제 링크: www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

1. 주의할 점

- DP를 이용하여 해결한다

- Int의 범위를 벗어날 수도 있으므로, Long Long으로 배열을 설정한다

 

2. 구현

- DP[][] 배열을 이용한다. 배열은 DP[숫자의 길이][끝나는 번호] 형태를 가지는 개수를 저장한다

- DP[1][]의 모든 원소는 1로 초기화한다

- DP[n][a]: DP[n-1][0]+DP[n-1][1]+...+DP[n-1][a]가 성립하므로 이에 점화식에 맞는 코드를 작성한다

 

#include <iostream>
using namespace std;
long long dp[1001][10];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int test,a;
    cin >> test;
    for(int i=0;i<10;i++)
        dp[1][i]=1;
    for(int i=2;i<=1000;i++)
        for(int j=0;j<10;j++)
            for(int k=j;k>=0;k--)
                dp[i][j]+=dp[i-1][k];
    for(int t=0;t<test;t++){
        cin>>a;
        long long sum=0;
        for(int i=0;i<10;i++)
            sum+=dp[a][i];
        cout <<sum<<'\n';
    }
    return 0;
}