백준 10844 (쉬운 계단 수)

문제

10844번: 쉬운 계단 수

45656이란 수를 보자.

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

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

---

규칙을 찾아보자.

N = 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 즉, 9개이다.

N = 2이면 10, 12, 21, 23, 32, 34, ...78, 87, 89, 98 즉, 17개 이다.

N = 3이면 101, 121, 123, 210, 212, .....878, 879, 898, 987, 989 즉, 32개이다.

 

규칙이 보이지 않는다.

처음에는 점화식을 dp[N] = x 로 정했다. N자릿수의 계단 수는 x개 란 의미이다.

하지만 이렇게 하는 것은 dp를 사용할 필요가 없었다. 따라서 다른 방법을 구해야 한다.

 

만들어 놓은 숫자의 일의자리에 따라 현재 숫자의 영향을 미친다.

예를 들어 N= 2 중에서 숫자가 10으로 끝났으면 N=3 중에서 101 밖에 경우의 수가 없다.

예를 들어 N=2 중에서 숫자가 56으로 끝났으면 N=3 중에서 565, 567이 있다.

예를 들어 N=2중에서 숫자가 89로 끝났으면 N=3중에서 898 밖에 경우의 수 가 없다.

 

이를 정리하면 끝자리 수가 0 또는 9면 1개 밖에 없고, 나머지 숫자 1 ~ 8인 경우 2개가 나온다.

dp[n][i] = x

길이가 n인 계단 수 중에서 끝 숫자가 i인 경우의 수는 x개 이다.

 

처음에 dp[1][1], dp[1][2], dp[1][3], ...dp[1][9] = 1이다., dp[1][0] = 0 이다.

이제 점화식을 구해보자.

1. 끝자리가 0인경우 dp[i][0] = dp[i-1][1] 이다. (현재 끝자리가 0이 오는 경우는 이전 길이에서 끝자리가 1인 경우 이기 때문)

2. 끝자리가 9인경우 dp[i][9] = dp[i-1][8]이다. (현재 끝자리가 9가 오는 경우는 이전 길이에서 끝자리가 9인 경우 이기 때문)

3. 나머지 경우는 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.

---

전체 코드이다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        long [][]dp = new long [101][10];
        for(int i=1;i<=9;i++)dp[1][i] = 1;
        dp[1][0] = 0;

        for(int i=2;i<=n;i++){
            for(int j=0;j<10;j++){
                if(j==0)dp[i][j] = dp[i-1][1];
                else if(j==9)dp[i][j] = dp[i-1][8];
                else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];

                dp[i][j] %= 1000000000;
            }
        }

        long ans = 0;
        for(int i=0;i<=9;i++)ans+=dp[n][i];

        ans %= 1000000000;
        System.out.println(ans);
    }
}