[BAEKJOON] 백준 동적 계획법1 10844 :: 쉬운 계단 수

💬  문제 설명

45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

🔨  입출력 예

입력 

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

 

 

출력

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

   

예제 입력 1)

1

 

예제 출력 1)

9

 

예제 입력 2)

2

 

예제 출력 2)

17

​

​

💻  Main.java

• 이차원 배열 dy에 [계단수][현재 계단]으로 정보를 저장해준다.
• 계산한 모든 값을 1,000,000,000으로 나눠준다.
• 계단이 '0'일때는 '1'밖에 오지 못한다.
• 계단이 '9'일때는 '8'밖에 오지 못한다.
• 계단이 1~8이면 앞뒤로 i+1, i-1의 계단이 올 수 있다.

/* 백준 DP - 10844 :: 오르막 수 */
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		// dy[계단 수][현재 계단]
		long[][] dy = new long[n + 1][10];
		
		for(int i = 1; i < 10; i++) {
			dy[1][i] = 1;
		}
		
		// 두번쩨 자릿수부터 탐색
		for(int i = 2; i <= n; i++) {
			// i번째 자릿수의 가릿값들을 탐색 (0 ~ 9)
			for(int j = 0; j < 10; j++) {
				//	ㅓ=0, 자릿값이 0이면, 이전 자릿수의 첫번쨔 자릿수만 가능
				if(j == 0)
					dy[i][j] = dy[i - 1][1] % 1000000000;
				else if(j == 9)
					dy[i][j] = dy[i - 1][8] % 1000000000;
				else
					dy[i][j] = (dy[i - 1][j + 1] + dy[i - 1][j - 1]) % 1000000000;
			}
		}
		
		long total = 0;
		for(int i = 0; i < 10; i++)
			total += dy[n][i];
		
		System.out.println(total % 1000000000);
		
		sc.close();
	} 
}