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

처음엔 문제가 이해가 안되서 단순히 1-9,2-17,3-32, 4-54 의 수열 규칙을 이용해서 문제를 풀려고 했는데 잘못된 접근이었다.

~n일때까지 i번째 인덱스에서 만들수 있는 계단수갯수가 몇개인지를 계산하는 점화식을 만들어야 했다.

문제

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

예제입력 -> 출력

1 -> 9

2 -> 17

풀이과정

(1)규칙

• DP이므로 점화식을 이용합니다
• 첫째자리의 수는 1~9
• 둘째자리 수가 0이면 다음수는 1만 올 수 있습니다
• 9일 경우엔 다음수는 8만 올 수 있습니다
• 그외의 수 면 다음수는 n-1,n+1이 올 수 있습니다
• N자리의 계단수는, N자리 수 일때 각 숫자 0~9가 올수 있는 수의 총합입니다

(2)순서

n=3까지의 수를 만들어 봅니다.

n=1	1,2,3,4,5,6,7,8,9 (9개)
n=2	10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98 (17개)
n=3	101,121,123,212,234,232, .....(32개)

배열에 넣어서 표현해 보면, i번째순으로 만들수 있는 숫자의 갯수는

0 1 2 3 4 5 6 7 8 9

n=1         0 1 1 1 1 1 1 1 1 1 (9개)

n=2         1 1 2 2 2 2 2 2 2 1 (17개)

n=3         1 3 3 4 4 4 4 4 3 2 (32개)

이므로,

n=m 일 경우

0번째 인덱스는 d[m-1][1]

9번째 인덱스는 d[m-1][8]이고

나머지의 인덱스는 각 d[m-1][현재인덱스-1] + d[m-1][현재인덱스+1] 입니다.

각 인덱스에 맞는 작업을 한 뒤 %=1000000000를 해주고

각 합도 %1000000000 해주도록 합니다(각 인덱스의 합이 1000000000를 넘어가는 경우를 위해)

(3)코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<vector<int>> memo(N, vector<int>(10, 0));
    memo[0] = {0,1,1,1,1,1,1,1,1,1};//N이 1일경우
    for (int n = 1; n < N ; n++)
    {
        for (int i = 0; i < 10; i++)
        {
            if (i == 0)
                memo[n][i] = memo[n - 1][1];
            else if (i == 9)
                memo[n][i] = memo[n - 1][8];
            else
                memo[n][i] = memo[n - 1][i - 1] + memo[n - 1][i + 1];
            memo[n][i] %= 1000000000;
        }
    }
 
    int sum = 0;
    for (int j = 0; j < 10; j++)
    {
        sum += memo[N - 1][j];
        sum %= 1000000000;
    }
    cout <<  sum << endl;
    return 0;
}