[BAEKJOON] 10844 쉬운 계단

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; vector<vector<long long>> DP; //0을 만나면 1개 9를 만나면 1개 //나머지는 2개 long long go_step(int start_num, int count) { if (start_num < 0 || start_num > 9 || count<=0) return 0; long long &ret = DP[start_num][count]; if (ret != -1) return ret; return ret = go_step(start_num - 1, count - 1) % 1000000000 + go_step(start_num + 1, count - 1) % 1000000000; } int main() { int step; scanf("%d", &step); DP = vector<vector<long long>>(10, vector<long long>(step + 1, -1)); for (int j = 1; j < 9; j++) DP[j][1] = 2; DP[0][1] = 1; DP[9][1] = 1; long long answer = 0; if (step == 1) { printf("%d", 9); return 0; } for (int j = 1; j < 10; j++) answer += go_step(j, step - 1) % 1000000000; printf("%d",answer % 1000000000); return 0; } //#define _CRT_SECURE_NO_WARNINGS //#include <iostream> //#define R 1000000000 //int n, s, k = 1, d[2][11]; //int main() { // int i, j; // for (j = 1; j <= 9; j++) d[k][j] = 1; // scanf("%d", &n); // for (i = 2; i <= n; i++) { // k = !k; // for (j = 0; j < 10; j++) d[k][j] = (d[!k][j - 1] + d[!k][j + 1]) % R; // } // for (j = 0; j<10; j++) s = (s + d[k][j]) % R; // printf("%d", s); // return 0; //}