45656
이 수는 모든 자리수의 차이가 1이 난다. 이런 수가 계단수.
첫째 줄에 N이 주어지고 N은 1<=N<=100
10^100까지 커질 수 있다. 브루트포스로 할 수 있는 크기가 아니다.
이걸 알고서도 점화식 떠오르는게 없어서 브루트포스처럼 bottom-up으로 푸는 점화식을 생각했다.
D[N] : N의 계단 수인지 아닌지
S[N] : N의 자리수
D[N] = D[S[0] + S[1]] || D[S[1] + S[2]] || D[S[n-2] + S[n-1]]
// D[N]이 true면 cnt++;
n이 10^100인 경우, 최악의 경우 10^99 * 10^100 인데, 시간초과 날 수 밖에 없다.
걍 풀이를 보자.
D[N] => 길이가 N인 계단수.
위 점화식은 마지막 수에 대한 정보를 담고 있지 않다. (갑자기?)
점화식을 정의하기 위해 자리수별로 점화식을 세우려는 의도같다.
D[N][L] : 마지막 수가 L이고 길이가 L인 계단 수
? ? L+1 | L-1 L
[1][2]... [N-1] [N]
L앞에 올 수 있는 수는 L-1, L+1인데, 이 때 계단 수는 D[N-1][L+1], D[N-1][L-1] 즉, D[N][L] = D[N-1][L-1] + D[N-1][L+1]
풀어보자.
long long dp[101][10];
long long n;
cin>>n;
long long size = n;
long long mod = 1000000000;
// fill_n(dp, size, 0); // 0: 미정, 1: true, -1: false
for(int i = 1; i<=9; i++) {
dp[1][i] = 1;
}
for(int i = 2; i<=size; i++) {
for(int j = 0; j<=9; j++) {
dp[i][j] = 0;
if(j-1>=0) {
dp[i][j] += dp[i-1][j-1];
}
if(j+1<=9) {
dp[i][j] += dp[i-1][j+1];
}
dp[i][j] %= mod;
}
}
long long result = 0;
for(int i = 0; i<=9; i++) {
result += dp[size][i];
}
cout<<result % mod<<endl;
Summary
자리 수 문제는 자리수 별로 점화식을 세워서 풀 수 있다는 생각을 해야겠다.
