[BOJ] 10844: 쉬운 계단 수(JAVA)

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

10844번: 쉬운 계단 수

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

 

---

[문제 풀이]

2차원 정수 배열 dp를 (N+1) * 10 크기로 선언한다.

dp[i][j]에서 i는 자릿수를 의미하고, j는 i번째 자리에 오는 수를 의미한다.

끝자리부터 계산한다고 생각하면 된다. 

예를 들어 dp[1][1]는 자릿수가 1일 때 마지막 자리에 1이 오는 경우의 수이다.

i가 1일 때는 한자릿수일 때이므로 1~9까지 각 경우의 수는 1이다.

따라서 dp[1]~dp[9]까지 1로 초기화시킨다.

 

i가 2일때,

자릿수는 2이고, 만약 마지막 자릿수가 0이었다면 올 수 있는 수는 1밖에 없다.

예를 들어 *0이면, 앞에 올 수 있는 수는 1밖에 없는 것이다. 따라서 j==0이면, 1이 오는 경우만 고려하면 되므로

dp[i][0] = dp[i-1][j+1] % 1000000000; 이 된다.

마지막 자릿수가 9였다면 올 수 있는 수는 8밖에 없다.

*9이면 9보다 큰 한자리수는 없으므로 8이 오는 경우만 고려하면 된다.

따라서 dp[i][9] = dp[i-1][j-1] % 1000000000; 이 된다.

그 외의 경우(1~8)는 올 수 있는 수가 해당 수보다 1 작은 수, 1 큰 수 두 가지가 올 수 있다.

따라서 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000; 이 된다.

	0	1	2	3	4	5	6	7	8	9	sum
1	0	1	1	1	1	1	1	1	1	1	9
2	1	1(=0+1)	2(=1+1)	2(=1+1)	2(=1+1)	2(=1+1)	2(=1+1)	2(=1+1)	2(=1+1)	1	17
3	1	3(=1+2)	3(=1+2)	4(=2+2)	4(=2+2)	4(=2+2)	4(=2+2)	4(=2+2)	3(=2+1)	2	32

위의 표와 같은 방식으로 진행되게 되며, sum은 dp[i][0]~dp[i][9]까지 더한 수이다.

 

dp[N][0]~dp[N][9]까지 다 구하고 나면 sum을 구해 반환하면 된다.

 

[코드]

import java.util.*;

public class Main{

	public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N =sc.nextInt();
         int[][] 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=0;j<10;j++) {
        		 if(j==0)	
        			 dp[i][j] = dp[i-1][j+1] % 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 sum=0;
         for(int i=0;i<10;i++)
        	 sum+=dp[N][i];
         
         System.out.println(sum%1000000000);
        
	}
}