45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
입력 | 출력 |
---|---|
1 | 9 |
2 | 17 |
d[N][j]
: N자리수 중 끝 자리가 j인 숫자.<Base Case>
<Recursive Case>
#include <iostream>
using namespace std;
int n, d[101][11];
long long ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>n;
//L(1)값에 대해 초기화 해주기
d[1][0]=0;
for(int i=1;i<10;i++) d[1][i]=1;
//계산
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
if(j==0) d[i][j]=d[i-1][j+1]% 1000000000;
else if(j==9) d[i][j]=d[i-1][j-1]% 1000000000;
else d[i][j]=(d[i-1][j-1]+d[i-1][j+1])% 1000000000;
}
}
//결과는
for(int i=0;i<=9;i++) ans+=d[n][i];
cout<<ans%1000000000;
return 0;
}
d[N]
이라는 결과값을 도출하는 과정에서도 long long형의 가용 범위를 넘어간다. 그래서 중간 결과에서도 모듈로 연산이 수행되어야 하는게 맞다.(15+17)%10=2
(15%10+17%10)%10=2
d[N][j]
배열을 생각해내는 것이 나에겐 어려웠다. 단순히 d[N]
으로만 받아서 계산하려고 했는데 끝 자리수에 따라서 다음 결과에 영향을 미치기 때문에 단순히 으아~복잡해 하고 생각했다.