(C언어) 백준 10844번 : 쉬운 계단수 - 컴도리돌이

백준 10844번 : 쉬운 계단수

---

문제

45656이란 수를 보자.

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

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

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

---

입력

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

출력

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

---

 

 

#include <stdio.h>
#define mod 1000000000
int main(void){
    
    int n,sum = 0 ,DP[101][10] = {0,};

    scanf("%d", &n);

    for (int i = 0; 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][0] = DP[i - 1][1] % mod;
            else if (j == 9)
                DP[i][9] = DP[i - 1][8] % mod;
            else
                DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % mod;
        }
    }
    for (int i = 1; i < 10; i++)
    {
        sum = (sum + DP[n][i]) % mod;
    }
    printf("%d", sum % mod);
}

 

 

 

 

요번 문제는 다른 블로그에서 푸신 분의 코딩을 보고 참고하였습니다. 이 문제를 푸는데 4시간이 걸렸고, 3번이나 틀린 후에 겨우 맞았습니다...ㅠㅠ 분명히 제가 만든 경우의 수에서 다 돌아갔는데, 제출만 하면 틀리더라고요.. 이 허무함.

요번 DP문제는 규칙을 찾는게 정말 힘듭니다. N의 계단수 와 그 계단수에서 1~9가 나올 경우의 수를 이중 배열을 사용해서 규칙을 찾아야 겨우 풀 수가 있습니다.

 

-제목이 왜 쉬운 계단수인지 아직도 의문이네요;;