2688번

2688번 - 줄어들지 않아

처음에 완전탐색으로 풀었지만, 시간초과, 시간초과가 날 줄은 알고 있었다.

그래서 DP를 이용해서 풀었다. 처음에는 1차원 DP로 했더니 틀렸다.. 그래서 하나씩 써보면서 보니까

바로 오류가 있다는 것을 알아냈다. 그래서 2차원 DP를 이용했다.

D[n][k] = n자리 숫자이고 이전에 사용한 숫자가 k 일때, 만들 수 있는 경우의 수

<정답 코드>

#include<iostream>
 
using namespace std;
int n;
long long D[65][10];
long long go(int k,int pre)
{
    if (k == 0)
    {
        return 1;
    }
    
    if (D[k][pre] > 0)
    {
        return D[k][pre];
    }
 
    for (int i = 0; i <= 9; i++)
    {
        if (i >= pre)
        {
            D[k][pre] += go(k - 1, i);
        }
    }
 
    return D[k][pre];
}
 
int main()
{
    int tc;
    cin >> tc;
 
    while (tc--)
    {
        cin >> n;
        cout << go(n,0) << "\n";
    }
 
    return 0;
}