[D-3] 10844 : 계단 수 구하기(Java)

📍 백준 10844번

시간제한 메모리제한 제출정답 정답맞힌 사람 정답 비율
2 초 128 MB 16320 4923 3808 34.168%

✅ 문제

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

✅ 입력

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

✅ 출력

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

예제 입력 1
1
예제 출력 1
9
예제 입력 2
2
예제 출력 2
17

✅ 정답 코드

import java.util.Scanner;
 
public class Main {
	
	static Long[][] dp;
	static int N;
	final static long MOD = 1000000000;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		N = in.nextInt();
		dp = new Long[N + 1][10];
		
		// 첫번째 자릿수는 1로 초기화 
		for(int i = 0; i < 10; i++) {
			dp[1][i] = 1L;
		}
		
		long result = 0;
		
		// 마지막 자릿수인 1~9까지의 경우의 수를 모두 더해준다.
		for(int i = 1; i <= 9; i++) {
			result += recur(N, i);
		}
		System.out.println(result % MOD);
	}
	
	/*
	 dist 는 자릿수, val은 자릿값을 의미함
	 
	 첫째 자리수는 각 val이 끝이기 때문에
	 경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
	 1로 초기화 되어있어야한다.
	*/
	
	static long recur(int digit, int val) {		
 
		// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
		if(digit == 1) {
			return dp[digit][val];
		}
			
		// 해당 자리수의 val값에 대해 탐색하지 않았을 경우 
		if(dp[digit][val] == null) {
			// val이 0일경우 이전 자리는 1밖에 못옴
			if(val == 0) {
				dp[digit][val] = recur(digit - 1 ,1);
			}
			// val이 1일경우 이전은 8밖에 못옴
			else if(val== 9) {
				dp[digit][val] = recur(digit - 1, 8);
			}
			// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
			else {
				dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
			}
		}
		return dp[digit][val] % MOD;
	}
}