[백준, BOJ 10844] 쉬운 계단 수 (java)

출처-https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

728x90

내가 푼 방식

: dp[i][0]는 dp[i-1][1]일 경우에만 올 수 있다.

  dp[i][j=1]~dp[i][j=8]은 각각 dp[i-1][j-1]와 dp[i-1][j+1]인 경우에 올 수 있다.

  dp[i][9]는 dp[i-1][8]일 경우에만 올 수 있다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		long dp[][]=new long[n+1][10];
		long cases=0;
				
		for (int i=1;i<10;i++)
			dp[1][i]=1;
		
		for (int i=2;i<=n;i++) {
			dp[i][0]=dp[i-1][1]%1000000000;
			for (int j=1;j<9;j++)
				dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
			dp[i][9]=dp[i-1][8]%1000000000;
		}
		for (int i=0;i<10;i++)
			cases+=dp[n][i];
		cases%=1000000000;
		System.out.println(cases);
	}

}