[백준] 2688 - 줄어들지 않아
1. 문제
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