백준 2688번 : 줄어들지 않아

  어떤 것을 dp 배열로 저장할 것인지만 잘 정하면 어렵지 않은 문제였다.

 

dp[n][k]?

줄어들지 않는 n자리 수 중 1의 자리가 k인 숫자의 갯수

 

  n의 범위가 64까지이고 1의 자리의 범위는 0부터 9까지이므로 dp의 최대 크기는 dp[65][10]이면 충분하지만 for을 한 번이라도 줄이기 위해 dp[65][11]까지 만들고 11번째 열에 그 행의 합을 저장했다.

 

행은 숫자의 자리수, 열은 1의 자리 수를 나타낸다. 즉, 4행 6열은 줄어들지 않는 4자리 수 중 일의 자리가 6인 수의 개수이다.

 

  나는 기존의 줄어들지 않는 수의 마지막에 새로운 숫자를 붙이는 방식으로 자리수를 늘려나가는 방식을 생각했다. 따라서 1의 자리수를 알고 있다면 새로운 수를 붙일 때 1의 자리수보다 작지 않은 수를 붙이면 된다.

 

  예를 들어 줄어들지 않는 5자리 숫자 중 1의 자리가 4인 수의 개수, 즉 dp[5][4]를 구하려한다고 생각해보자. 그렇다면 줄어들지 않는 4자리 숫자의 뒤에 숫자 4를 붙였을 때도 줄어들지 않는 수가 되어야 하기 때문에 4자리 수의 1의 자리 숫자로 가능한 숫자는 0, 1, 2, 3, 4이다.

 

dp[5][4] = dp[4][0] + dp[4][1] + dp[4][2] + dp[4][3] + dp[4][4]

 

  이 과정을 모든 자리 수에 대해 쭉 진행을 해서 dp를 채워놓은 뒤 각 케이스 맞는 값들을 출력해줬다.

 

#include <iostream>

using namespace std;

int t;
long long dp[65][11];

int main()
{
    for(int i = 0; i < 10; i++)
    {
        dp[1][i] = 1;
    }
    dp[1][10] = 10;
    
    for(int i = 2; i <= 64; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            for(int k = 0; k <= j; k++)
            {
                dp[i][j] += dp[i-1][k];
            }
            dp[i][10] += dp[i][j];
        }
    }
    
    cin >> t;

    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        
        cout << dp[n][10] << "\n";
    }
    
    return 0;
}