[백준] 10844 쉬운 계단 수 - 자바(Java)

10844번

쉬운 계단 수

 

 

 

문제

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

 

 

 

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

10844번: 쉬운 계단 수

---

• 작은 문제의 답을 구하여 규칙을 구한다

 

dp[1] = 9

dp[2] = 17

dp[3] = 32

dp[4] = 61

...

 

???

 

알고리즘을 하나 씩 설계해보자.

 

 

 

• 알고리즘을 설계해보자

 

1. 만약 n번째 자리의 수가 0 혹은 9일 경우, 다음에 올 수 있는 수는 각각 1, 8로 경우의 수가 1가지씩 나온다.
   • dp[n][x] = dp[n-1][1]
   • dp[n][x] = dp[n-1][8]
2. n번째 자리의 수가 0, 9가 아닌 다른 수 일 경우, 다음에 올 수 있는 숫자의 경우의 수는 2이다.
   • dp[n][x] = dp[n-1][x-1] + dp[n-1][x+1]
3. n번째 자리수를 사용해야함으로, 2차원 배열 dp[][]를 사용한다.
   • Top-down 방식을 사용하여 재귀함수를 이용한다면, 매개변수를 2개 가져와야한다.
   • 따라서, 첫 큰 문제의 n번째 자리수를 1에서 9까지 탐색할 수 있도록, main에서 반목문으로 탐색해 주어야 한다.
4. 1,000,000,000은 매번 나누어 준다. (오버플로우)

 

 

 

 

 

 

 

 

 

 

 

 

이를 재귀함수를 이용한 Top-down 방식을 이용하여 나타내면,

import java.util.*;

public class B10844______ {
    static Long dp[][];
    static int num;

    public static void main(String[] arg) {
        Scanner input = new Scanner(System.in);

        num = input.nextInt();

        dp = new Long[num + 1][10];
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1L;
        }

        int sum = 0;

        for (int i = 1; i < 10; i++) {
            sum += count(num, i);
        }

        System.out.println(sum % 1000000000);

    }

    static long count(int n, int x) {

        if (n == 1) {
            return dp[n][x];
        }
        if (dp[n][x] == null) {
            if (x == 0) {
                dp[n][0] = count(n-1, 1);
            } else if (x == 9) {
                dp[n][9] = count(n-1, 8);
            } else {
                dp[n][x] = count(n-1, x+1) + count(n-1, x-1);
            }
        }
        return dp[n][x] % 1000000000;
    }
}

와 같다.

 

 

 

 

tip) nullpointer 오류가 나지 않도록 dp의 0, 1, 2 등의 값을 초기화 해주어야 한다.

tip) 위의 코드의 경우, dp[1][0~9]의 값을 1로 반복문을 이용하여 초기화 해주었다.