백준 10844번: 쉬운 계단 수 [DP] - Java

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

쉬운 계단 수라면서 하나도 쉽지 않았다. 완전 어려운 계단 수임

 

n이 1~4일때의 경우의 수를 다적었다.

 

n==1

1

2

3

4

5

6

7

8

9

 

n==2

10 12

21 23

32 34

43 45

54 56

65 67

76 78

87 89

98

....

 

n자리의 수 중에 1로 시작하는 계단 수는 (n-1의 9로 시작하는 수+ n-1 2~7로 시작하는 수)

2~8로 시작하는 계단 수는 (n-1의 현재 시작수 +1 -1 ) ex. 3으로 시작하는 수라면 2와 4 

9는 n-1의 8자리의 수이다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static int[][] dp;
	public static void main(String[] args) {


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

}