문제
풀이
dp[i][j]를 i개의 자릿수를 가지는 끝자리가 j인 쉬운 계단 수라고 정의한다. 쉬운 계단 수 중 끝자리가 0인 경우는 그 다음 자릿수의 끝자리가 오직 1로만 되고 같은 식으로 끝자리가 9인 경우는 오직 8로만 된다. 예를 들어, 10과 89는 오직 다음 자릿수의 쉬운 계단 수를 101, 898로만 만들어낸다. 그 나머지 경우는 각각 끝자리 수 + 1, 끝자리 수 - 1 을 이어 붙인 식으로 쉬운 계단 수를 만들어 낸다. 그러므로 점화식은 dp[i][j] = dp[i-1[j-1] + dp[i-1][j+1] 이며, 끝 자리 수가 0과 9인 경우는 각각 dp[i][j] = dp[i][j+1], dp[i][j] = dp[i][j-1]이 될 것이다.
소스 코드
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
#include <iostream>
using namespace std;
long long dp[100][10];
int main(){
int N;
scanf("%d", &N);
for(int i = 1; i<10; i++){
dp[1][i] = 1;
}
dp[1][0] = 0;
for(int i = 2; i<=N; i++){
for(int j = 0; j<10; j++){
if(j == 0) dp[i][j] = dp[i-1][j+1]%1000000000;
else if(j == 9) dp[i][j] = dp[i-1][j-1]%1000000000;
else dp[i][j] = (dp[i-1][j+1] + dp[i-1][j-1])%1000000000;
}
}
long long cnt = 0;
for(int i = 0; i<10; i++){
cnt = cnt + dp[N][i];
}
printf("%lld\n", cnt%1000000000);
}
