백준 10844번 - 쉬운 계단 수(C언어)

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

문제 풀이

---

#include <stdio.h>

int main(void)
{
    int n = 0;
    long sum = 0;
    long dp[101][10];

      scanf("%d", &n);
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }

    for(int i =2; i <= n; i++)
    {
        for(int j = 0; j <= 9 ; 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]) % 1000000000;    
        }
    }
    for (int i = 0; i < 10; i++) {
        sum += dp[n][i];
    }
    printf("%d", sum % 1000000000);

    return 0;
}

문제를 풀며 동적 계획법(Dynamic Programming)이라는 것을 발견했고, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장해 다시 큰 문제를 해결할 때 사용하는 알고리즘은 아니고 문제해결 방식이라고 본다.
① 동일한 작은 문제들이 반복해서 나타날 때.
② 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적의 결과를 낼 때

①, ② 조건을 만족한다면 동적 계획법의 방식으로 접근하면 좋다.

• ① = N = k(임의의 자연수)일 때, (k-1)번째까지의 결과를 사용한다는 점.
• ② = N = 1일 때의 결과를 사용해 전체 문제를 사용한 다는 점.