2. 문제 요약: 인접한 수끼리의 차이가 1인 수를 계단 수라고 한다. N이 주어졌을 때, 길이가 N인 계단 수는 모두 몇 개인가?
3. 문제 접근 방법: 다음과 같이 작은 문제로 나눈다.
길이가 1인 계단수의 개수 -> 길이가 1이고 끝이 0인 계단수의 개수, 길이가 1이고 끝이 1인 계단수의 개수...
길이가 2인 계단수의 개수
길이가 3인 계단수의 개수
...
길이가 N인 계단수의 개수
여기서 중요한 점은, 만일 우리가 길이가 k인 계단수를 구하려고 할 때, 길이가 k-1인 계단수에 대한 계산이 끝났다면 안심하고 그 값을 사용해도 된다는 점이다.
왜냐하면, 어떠한 계단수가 있을 때 그 계단수를 아무렇게나 잘라 내어도 잘려진 두 수 역시 계단수여야 하기 때문이다.
직관적으로 당연하고, 귀류법으로 증명할 수 있다.
4. 문제에 얽힌 슬픈 이야기: 원래는 [쉬운 계단 수]가 아니라 [계단 수] 문제를 풀고 있었는데, 그 문제는 "0에서 9까지의 수가 모두 포함된 계단수"만 세는 문제였다. 그걸 모르고 멍청하게 코딩하다가, 예제-입력 값이 뭔가 이상하다는 걸 깨닫고 [쉬운 계단 수]문제를 찾아 풀었다.
참고로 [계단 수] 문제 정답률이 [쉬운 계단 수]보다 더 높은데, 난이도는 정반대다.
5. C 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <stdio.h>
#include <stdlib.h>
#define divisor 1000000000
int main()
{
int result = 0;
int N;
scanf("%d", &N);
int **dp = (int**)malloc(sizeof(int*) * (N + 1));
for(int i = 0; i <= N; i++)
{
dp[i] = (int*)malloc(sizeof(int) * 10);
for(int j = 0; j < 10; j++)
dp[i][j] = 0;
}
for(int i = 1; i < 10; i++)
dp[1][i] = 1;
for(int i = 2; i <= N; i++)
{
for(int j = 0; j < 10; j++)
{
if(j - 1 >= 0)
{
dp[i][j] += dp[i - 1][j - 1];
dp[i][j] %= divisor;
}
if(j + 1 <= 9)
{
dp[i][j] += dp[i - 1][j + 1];
dp[i][j] %= divisor;
}
}
}
for(int i = 0; i < 10; i++)
{
result += dp[N][i];
result %= divisor;
}
printf("%d\n", result);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기