[백준] 11057 - 오르막 수

1. 문제

11057번: 오르막 수

2. 개요

오르막 수란, 수의 자리가 오름차순을 이루는 수를 말한다.

인접한 자리의 수가 같은 수여도 오름차순으로 친다. ex) 1113, 2245 …

이 때, 길이가 N인 오르막 수의 개수를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

2차원 dp테이블을 만든다.

i자리인 수 중 j로 끝나는 오르막 수의 개수를 나타낸다.

대강 표를 만들어 값을 확인하면 dp[i, j] = dp[i-1, j] + dp[i, j-1]임을 알 수 있다.

이를 활용해 정답을 도출, 출력한다.

3-2. Python

import sys

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

dp = [[1] + [0 for i in range(9)] for j in range(N + 1)]

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

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

print(sum(dp[N]) % 10007)

3-3. C#

namespace boj_11057
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            long[,] dp = new long[N + 1, 10];
            long answer = 0;

            for (int i = 1; i < N + 1; i++)
            {
                if (i == 1)
                {
                    for (int j = 0; j < 10; j++)
                    {
                        dp[i, j] = 1;
                    }
                }

                else
                {
                    dp[i, 0] = 1;

                    for (int j = 1; j < 10; j++)
                    {
                        dp[i, j] = (dp[i - 1, j] + dp[i, j - 1]) % 10007;
                    }
                }
            }

            for (int i = 0; i < 10; i++)
            {
                answer += dp[N, i];
            }

            Console.WriteLine(answer % 10007);
        }
    }
}