package backjoon;
/*문제
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1000000000으로 나눈 나머지를 출력한다.*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class back10844 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long stair[][] = new long[101][11];
stair[1][0] = 0;
//1일 경우 0부터 시작할 수 없으니까 1부터 1로 만들어줌.
for(int i=1; i<11; i++) stair[1][i] = 1;
for(int i=2; i<=n; i++){
for(int j=0; j<10; j++){
if(j==0){
stair[i][j] += (stair[i-1][j+1] % 1000000000);
}else if(j>0 && j<9){
stair[i][j] += (stair[i-1][j-1] + stair[i-1][j+1]) % 1000000000;
}else stair[i][j] += (stair[i-1][j-1] % 1000000000);
}
}
long total = 0;
for(int i=0; i<10; i++) total += stair[n][i];
System.out.println(total % 1000000000);
}
}
댓글
댓글 쓰기