백준 10844번 - 쉬운 계단 수

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

반례

 

계단 수는 0으로 시작하면 안되며 인접한 숫자마다 1의 차이를 가져야한다.

따라서 아래 그림과 같이 경우의 수를 나열해볼 수 있다.

 

경우의 수

 

여기서 N=3 일 때 뒤 2자리는 N=2 인 경우에서 가져온다는 규칙을 알 수 있다. 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long dp[][] = new long[N+2][10];
		long sum=0;
		final long div = 1000000000;
		
		for(int i=1;i<10;i++)
			dp[1][i]=1;
		
		for(int i=1;i<9;i++){
			dp[2][i]=2;
		}
		dp[2][0]=1;
		dp[2][9]=1;
		
		if(N>2)
		{
			for(int i=3;i<N+1;i++)
			{
				dp[i][0]=dp[i-1][1]%div;
				for(int j=1;j<9;j++)
				{
					dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%div;
				}
				dp[i][9]=dp[i-1][8]%div;
			}
		}
		
		for(int i=1;i<10;i++)
		{
			sum += dp[N][i];
			sum%=div;
		}
		System.out.println(sum);
	}
}