[백준 C++] 10844번 쉬운 계단 수

10844번: 쉬운 계단 수

문제 요약

문제

45656이란 수를 보자.

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

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

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. ``` 예제1

입력 1 출력 9

## 풀이
마지막 숫자를 기준으로 dp를 진행한다. 다른 한 축은 숫자의 길이로 하여 이차원 dp로 한다. 자리수가 늘어날 수록 전 자리수에서 마지막 숫자가 현재 숫자와 1차이 나는 것만큼 둘이 더하여 풀면 된다. 

## 어려웠던 점


## 배운 점 / 느낀 점


## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000000
using namespace std;

int n;
vector<vector<int>> num;
vector<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    num = vector<vector<int>>(n+1, vector<int>(10, 0));
    s = vector<int>(n+1);
    num[1] = {0,1,1,1,1,1,1,1,1,1};
    s[1] = 9;
    for(int i = 2; i <= n; i++){
        for(int j = 0; j < 10; j++){
            num[i][j] = 0;
            if(j-1 >= 0){
                num[i][j] = (num[i][j] + num[i-1][j-1]) % MOD;
            }
            if(j+1 < 10){
                num[i][j] = (num[i][j] + num[i-1][j+1]) % MOD;
            }
            s[i] = (s[i] + num[i][j]) % MOD;
        }

    }
    cout << s[n];
    return 0;
}