[백준] 10844번 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

# 문제

 

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

# 입력

 

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

 

# 출력

 

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

 

# 예시 입력

1

2

# 예시 출력

9

17

---

개인적으로 오랜 시간을 들인 문제였다... 계단 수라는 것을 보고 당황하고, 길이가 N인 계단 수를 출력하라니 어디서부터 시작해야할지 한참을 갈피를 못잡았다. 1 2 3 4 5 6 7 8 9는 계단 수라는 단어 정의에 어긋나는 것 같지만 초기값을 위하여 허용한 것 같다. 0으로 시작하는 수는 불허하며 각 자릿수에서 인접한 수는 반드시 -1/+1 인 수 이어야 한다. 동적 프로그래밍 문제인데 사실 왜 동적 프로그래밍 문제였는지 조차 몰랐다. A4 한장을 가득 채워갈 때 쯤 2차원 배열에 담아야 한다는 생각이 들었다. int[][] arr = new int[x+1][10]에다가 값을 담는 것이다. 근데 어떤 값을 담아야 할까?

 

N = 1일 때, [1 2 3 4 5 6 7 8 9] 이므로 9개 그럼 1행의 값은 다음과 같을까?

arr[1][1] = 1, arr[1][2] = 2, arr[1][3] = 3, ... arr[1][9] = 9

결론은 NO 이다. 문제의 본질을 생각해보면 '개수'를 구하는 문제이므로 각 열은 0의 개수, 1의 개수, 2의 개수, ..., 9의 개수이다.

즉 arr[1][] = [0 1 1 1 1 1 1 1 1 1]이다. arr[1][0] ~ arr[1][9]의 값을 모두 더하면 9가 된다. 그럼 arr[2][]의 값들은 어떻게 되는 것 일까?

 

N = 2: 17개

10	21	32	43	54	65	76	87	98
11	22	33	44	55	66	77	88	99
12	23	34	45	56	67	78	89	X

99에서 하나 올리면 100이 되므로 N = 2의 조건에 어긋난다. 위 표의 일부를 조금 더 시각적으로 보자면 다음과 같다.

 

        10            21           32          43                          98

    ↗            ↗             ↗           ↗                        ↗

11             22          33            44             ...          99

    ↘            ↘             ↘           ↘                        ↘

        12            23           34            45                         X

 

아.. N = 2일 때 길이가 2인 계단수의 개수는 10의 자리는 필요없고, 1의 자리에 있는 수가 '몇 개'인지 구하면 된다.

0	1	2	3	4	5	6	7	8	9	합
1개	1개	2개	2개	2개	2개	2개	2개	2개	1개	17

> 1~8은 2개의 숫자를 배출할 수 있다. 

1 -> 0 | 1

2 -> 1 | 3

3 -> 2 | 4

4 -> 3 | 5

5 -> 4 | 6

6 -> 5 | 7

7 -> 6 | 8

8 -> 7 | 9

 

> 0과 9는 1개의 숫자만 배출할 수 있다.

0 -> X | 1

9 -> 8 | X

 

* 알고리즘

arr[1][1~9] = 1

for i=2 -> x then
   for j=0 -> 9 then
   
    	if(j == 0)? then
        	arr[i][j+1] += arr[i-1][j]
            
        else if(j == 0)? then
        	arr[i][j-1] += arr[i-1][j]
            
        else then
        	arr[i][j-1] += arr[i-1][j]
                arr[i][j+1] += arr[i-1][j]

# Whole Code </> - Java 11

public class Main {

    private final static long MOD = 1000000000;

    static long getAnswer(int x) {

        int[][] arr = new int[x+1][10];

        for(int i=1; i<=9; i++) arr[1][i] = 1;

        for(int i=2; i<=x; i++)
            for(int j=0; j<=9; j++)
                if(j == 0)
                    arr[i][j+1] += arr[i-1][j] % MOD;

                else if(j == 9)
                    arr[i][j-1] += arr[i-1][j] % MOD;

                else{
                    arr[i][j-1] += arr[i-1][j] % MOD;
                    arr[i][j+1] += arr[i-1][j] % MOD;
                }

        return IntStream.rangeClosed(0, 9).mapToLong(i -> arr[x][i]).sum() % MOD;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        if(x < 1 || x > 100) System.exit(0);

        System.out.printf("%d\n", getAnswer(x));
        sc.close();
    }
}