1. 문제 설명
계단 수는 특정 조건에 맞는 수를 세는 문제입니다.
주어진 수 N이 있을 때, N 자리의 계단 수를 구하는 문제를 다루겠습니다.
계단 수란 각 자리의 수가 그 다음 자리 수보다 1만큼 크거나 작아야 하는 수입니다. 예를 들어, 1234, 3210은 계단 수입니다.
그러나 1123, 2222는 계단 수가 아닙니다.
이 문제를 통해 동적 프로그래밍의 기본 아이디어와 구현 방법을 이해할 수 있습니다.
2. 입력 & 출력 형식
입력
N (1 ≤ N ≤ 100), 주어진 자연수인 N은 계단 수의 자리 수를 나타냅니다.
출력
N자리 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 출력합니다.
3. 문제 접근 방법
계단 수를 세기 위해서는 동적 프로그래밍(Dynamic Programming) 방식을 선택해야 합니다.
문제를 풀기 위해 다음과 같은 방법으로 접근할 수 있습니다.
N자리 계단 수를 구하기 위해, (N-1)자리 계단 수를 이용하여 값을 계산합니다.
다음과 같은 규칙을 찾아낼 수 있습니다:
- 각 자리 수가 0이면, 다음 자리 수는 1만 올 수 있습니다.
- 각 자리 수가 9이면, 다음 자리 수는 8만 올 수 있습니다.
- 각 자리 수가 1~8인 경우, 다음 자리 수는 그보다 1 작거나 큰 두 가지 선택이 가능합니다.
이를 바탕으로 DP 테이블을 구성하고, 각 자리수에 따른 계단 수를 기록해 나가면서
최종적으로 N자리 계단 수를 구할 수 있습니다.
DP 배열을 초기화하고, 점차적으로 채워나가는 방식으로 접근합니다.
4. C# 코드 구현
이제 본격적으로 C#으로 계단 수를 구하는 코드를 구현해 보겠습니다.
아래는 문제 해결을 위한 C# 코드입니다.
using System;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
long[,] dp = new long[N + 1, 10];
// 1자리 계단 수 초기화 (1~9)
for (int i = 1; i <= 9; i++)
{
dp[1, i] = 1;
}
// DP를 활용하여 N자리 계단수 구하기
for (int i = 2; i <= N; i++)
{
for (int j = 0; j <= 9; j++)
{
if (j == 0)
{
dp[i, j] = dp[i - 1, j + 1] % 1000000000; // 0 -> 1
}
else if (j == 9)
{
dp[i, j] = dp[i - 1, j - 1] % 1000000000; // 9 -> 8
}
else
{
dp[i, j] = (dp[i - 1, j - 1] + dp[i - 1, j + 1]) % 1000000000; // j-1, j+1
}
}
}
// N자리 계단수의 총합 계산
long result = 0;
for (int j = 0; j <= 9; j++)
{
result = (result + dp[N, j]) % 1000000000;
}
// 결과 출력
Console.WriteLine(result);
}
}
5. 코드 설명
위의 코드를 단계별로 설명하겠습니다.
1. 우선, 사용자의 입력으로부터 N을 읽어옵니다.
2. 2차원 배열 dp를 생성하여 dp[i, j]는 i자리의 계단 수 중 j로 끝나는 수의 개수를 저장합니다.
3. 1자리 수는 0~9 중에서 1~9만 사용 가능하므로 이를 초기화합니다.
4. 이후, 2자리부터 N자리까지 각 자리수를 계산합니다.
5. 각 자리수의 계산은 위에서 설명한 규칙에 따라 이루어집니다.
6. 마지막으로 N자리의 계단수를 모두 합산하여 결과를 출력합니다.
6. 복잡도 분석
이 알고리즘의 시간 복잡도는 O(N)입니다.
N이 100일 때, 2중 루프를 통해서 각 자리수에 대한 가능성을 확인하므로
O(N) * O(10) = O(N)에 해당합니다.
공간 복잡도는 O(N * 10)이며, 이는 메모리 사용량이 비교적 적다는 것을 의미합니다.
7. 예제
입력 예시
3
출력 예시
32
위의 예제에서 3자리 계단 수는 32개가 존재합니다.
이를 통해 문제를 이해할 수 있습니다.
8. 결론
이 강좌에서는 계단 수를 구하는 문제를 통해 동적 프로그래밍의 기초적인
개념을 익혔습니다.
계단 수 문제는 알고리즘 스킬을 향상시키는 데 도움이 되는 좋은 연습 문제가 될 수 있습니다.
다양한 문제를 풀어보면서 더 많은 경험을 쌓길 바랍니다.
앞으로도 알고리즘 문제 풀이에 도전하세요!