백준 | 10844번. 계단 수 구하기 - DP 문제

🟦 백준 10844번. 계단 수 구하기

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

풀이

• D[i][j] 의 정의 : i자릿수에서 j로 끝나는 계단 수 구하기
• 경우의 수 나누기
• 1) 0과 9의 경우, 1씩 차이나는 수가 각각 1, 8 밖에 없는 경계값이다.

	D[i][0] = D[i-1][1] ; //즉. i번쨰 자릿수에 0이 오면, i-1의 자릿수에는 1만 올 수 있다.
D D[i][9] = D[i-1][8] ; //즉. i번째 자릿수에 9가 오면, i-1(앞자리)에는 8만 올 수 있다.

• 2) 1~8 사잇값은 각각 2가지의 계단수가 올 수 있다.

D[i][j] = D[i-1][j-1] + D[i-1][j+1] ; 즉, 1~8 사잇수는 각각 계단수가 2개씩 존재

• 결과 코드

package to_0712_2;

import java.util.Scanner;

/*백준 10844번. 계단 수 */
public class Main {
	static final long MOD = 1000000000;
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		int N = kb.nextInt();
		long[][] D = new long[N+1][11];
		
		//초기화
		for(int i=1; i<=9; i++) {
			D[1][i] = 1;
		}	
		//값 세팅 
		for(int i=2; i<=N; i++) { //i로는 각 자릿수 찍을 거임 
			//i번째 끝자리에 0과 9가 오면, 직전 i-1번째 자리엔 각각 1과 8밖에 못 온다.  
			D[i][0] = D[i-1][1];
			D[i][9] = D[i-1][8];
			
			for(int j=1; j<=8; j++) {
				D[i][j] = (D[i-1][j-1] + D[i-1][j+1]) % MOD;
			}
		}
		//sum
		long sum = 0;
		for(int i=0; i<10; i++) {
			sum = (sum + D[N][i]) % MOD;
		}
		System.out.println(sum);
	}
}