[백준 10844번] 쉬운 계단 수

풀이

---

DP로 풀면 풀수있는 문제

일일이 경우의수를 써보면 규칙이있다.

1일때 1 1 1 1 1 1 1 1 1

2일때 2 2 2 2 2 2 2 2 1

3일때 2 4 4 4 4 4 4 3 2

소스코드

---

#include <iostream>
using namespace std;
 
int main() {
    int n, num[11], copy[11];
    long long sum=0;
    cin >> n;
    num[10] = 0;
    for (int i = 0; i <= 9; i++) {
        num[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        //복사
        for (int j = 0; j <= 9; j++) {
            if (j == 0) 
                copy[0] = num[1] % 1000000000;
            else if (j == 9) 
                copy[9] = num[8] % 1000000000;
            else 
                copy[j] = (num[j - 1] + num[j + 1])%1000000000;
        }
        //원상복귀
        for (int j = 0; j <= 9; j++) {
            num[j] = copy[j];
        }
    }
    for (int i = 1; i <= 9; i++) {
        sum = (sum + num[i])%1000000000;
    }
 
    cout << sum << '\n';
    return 0;
}