문제

백준 쉬운 계단 수 문제 보러가기



문제점 해결

이전에 오르막 수라는 백준 문제를 해결한 후 풀이해보면 좋은 문제이다.

N이 3이고 끝자리 수가 3일때를 가정해보자. _ _ 3 에서 3의 앞에 올 수 있는 숫자는 2와 4이다. 만약 2가 온다고 가정하면 _ 2 3 으로 2 앞에 올 수 있는 숫자는 1 또는 3이다. 이걸 식으로 만들어보면 dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] 이다.



풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] dp = new int[101][10];
		
		for (int i = 1; i < 10; i++) dp[1][i] = 1;
		
		for (int i = 2; i <= N; i++) {
			for (int j = 0; j < 10; j++) {
				if(j-1 >= 0) dp[i][j] += dp[i-1][j-1] % 1000000000;
				if(j+1 < 10) dp[i][j] += dp[i-1][j+1] % 1000000000;
			}
		}
		
		long answer = 0;
		for (long i : dp[N]) {
			answer += i;
		}
		
		System.out.println(answer%1000000000);
	}
}