1. 문제

2688번: 줄어들지 않아



2. 개요

맨 앞의 0도 포함하는 N자리 줄어들지 않는 수의 총 개수를 구하는 문제.



3. 풀이 및 코드

3-1. 풀이

[수의 자릿수][마지막 숫자]인 2차원 dp테이블을 만든다.

dp[i][j]의 값은 dp[i-1][0] + dp[i-1][1] + dp[i-1][2] … + dp[i-1][j] 이다.

이를 토대로 dp테이블을 채워나간 후, 각 테스트케이스에 대한 답으로 dp[i]의 총 합을 출력한다.

3-2. Python

import sys

dp = [[0 for i in range(10)] for j in range(65)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, 65):
    for j in range(10):
        for k in range(j + 1):
            dp[i][j] += dp[i-1][k]

T = int(sys.stdin.readline())

for t in range(T):
    print(sum(dp[int(sys.stdin.readline())]))

3-3. C#

namespace boj_2688
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            long[,] dp = new long[65, 10];

            for (int i = 0; i < 10; i++)
                dp[1, i] = 1;

            for (int i = 2; i < 65; i++)
            {
                for (int j = 0; j < 10; j++)
                {
                    for (int k = 0; k < j + 1; k++)
                    {
                        dp[i, j] += dp[i - 1, k];
                    }
                }
            }

            int T = int.Parse(sr.ReadLine());

            for (int t = 0; t < T; t++)
            {
                int n = int.Parse(sr.ReadLine());
                long answer = 0;
                for (int i = 0; i < 10; i++)
                    answer += dp[n, i];

                sw.WriteLine(answer);
            }

            sw.Close();
        }
    }
}

Comments