🏳 쉬운 계단 수 / 10844번 백준

문제

문제 난이도 : 실버 1

문제 분류 : 다이나믹 프로그래밍, 모듈러 연산 성질

---

문제 풀이

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    //Input
    int n = -1;
    cin >> n;
    vector<vector<long long int>> DP(n+1, vector<long long int>(12, 0)); // (Padding) 0 ~ 9 (Padding)

    //Main Logic
    DP[1][1] = 0;
    for (int i = 2; i < 11; i++)
    {
        DP[1][i] = 1;
    }


    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < 11; j++)
        {
            DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1];
            DP[i][j] %= 1000000000;
        }
    }
	
    //Output
    long long int Result = 0;
    for (int i = 1; i <= 11; i++)
    {
        Result += DP[n][i];
        Result %= 1000000000;
    }
    cout << Result;
}

---

참조

https://sskl660.tistory.com/75