백준 10844 쉬운 계단 수 (JAVA 자바 풀이)

백준 10844 쉬운 계단 수 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

 

⚔ 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

 

📣 출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

점화식 자체는 단순할 수 있지만 

케이스를 0일 때와 9일때로 나눠주는 부분에서 생각이 필요하다.

 

또한 자바의 경우 자료형을 신경써주어야 해서 이런 문제는 차라리 파이썬으로 푸는게 속편할 수 있다.

 

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static int N;

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		int mod = 1000000000;
		N = Integer.parseInt(bufferedReader.readLine());
		long[][] dp = new long[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 == 0) {
					dp[i][j] = dp[i - 1][1] % mod;
					continue;
				}
				if (j == 9) {
					dp[i][j] = dp[i - 1][8] % mod;
					continue;
				}
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1] ) % mod;
			}
		}
		long sum = 0;
		for (int i = 0; i < 10; i++) {
			sum += dp[N][i];
		}

		System.out.println(sum % mod);
	}
}