10844 쉬운 계단 수

 

아래 표에서,

dp[i][j] : j가 맨 뒤에 올 때의 계단수 개수

i = 1 일 때 계단수는,

j	0	1	2	3	4	5	6	7	8	9
계단수	x	1	2	3	4	5	6	7	8	9
dp[1][j]	0	1	1	1	1	1	1	1	1	1

 

i = 2 일 때 계단수는,

 

j	0	1	2	3	4	5	6	7	8	9
계단수	10	21	12 32	23 43	34 54	45 65	56 76	67 87	78 98	89
dp[2][j]	1	1	2	2	2	2	2	2	2	1

 

 

dp[2][4] 에서 j = 4 이고,

이때의 계단수인 34, 54는 (j-1) 4 , (j+1)4 이므로,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]  이다.

즉, dp[2][4] = dp[1][3] + dp[1][5]  = 1 + 1 = 2 이다.

즉,

길이가 2인 맨 끝에 4가 올 때의 계단수 개수

= 길이가 1인 맨 끝에 3이 올 때의 계단수 개수 + 길이가 1인 맨 끝에 5가 올 때의 계단수 개수 이다.   

 

이런식으로 구하면 된다.

 

이때 j= 0, 9  일 때는 예외인데,

j= 0 일 때

바로 앞에 1밖에 올 수가 없다.

예를 들어 dp[2][0] = 1 로, 계단수는 10이 될 수 있다.

 

또 j=9일 때는

바로 앞에 8밖에 올 수 없다.

dp[2][9] = 1 로, 계단수는 89가 있다.

 

때문에 이 경우만 각각

j=0 일 때는

dp[i][j] = dp[i - 1][j + 1]

 

j=9 일 때는

dp[i][j] = dp[i-1][j-1] 를 사용하면 된다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
   
 
  
    public static void main(String[] args) throws Exception{
   
    	
    	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      	 int N = Integer.parseInt(st.nextToken());
      	 int number = 1000000000;
      	 long dp[][] = new long[101][101];
      	 
      	 for(int j=1; j<=9; j++) {
      		 
      		 
      		 dp[1][j] = 1;
      		 
      	 }
      	 
      	 
      	 for(int i = 2; i<=N; i++) {
      		 
      		 
      		 for(int j = 0; j<=9; j++) {
      			 
      			 
      			 if(j==0) {
      				 
      				 dp[i][j] = dp[i-1][j+1]%number;
      				 
      			 }else if (j==9) {      				 
      				 
      				 dp[i][j] = dp[i-1][j-1]%number;
      				 
      			 }else {
      				 
      				 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%number;
      			 
      			 }
      			 
      		 }
      		 
      	 }
      	 
      	 
      	 long result = 0;
      	 
      	 for(int j=0; j<=9; j++) {
      		result+=dp[N][j];
      	 }
      	 System.out.println(result%number);
      	 
      	 
    	}
    }