[BAEKJOON] 10844 쉬운 계단 수

#include <iostream> #include <fstream> #include <vector> using namespace std; #define MOD 1000000000 int input; vector<vector<long long>>cache; //첫번째 : 자리수 & 두번째 : 숫자 long long check_stair(int index, int num, int before_num) { if (index < 0 || num < 0 || num > 9) return 0; if (index >= input) return 1; long long & ret = cache[index][num]; if (ret != 0) return ret; return ret += (check_stair(index + 1, num - 1, num) + check_stair(index + 1, num + 1, num)) % MOD; } int main() { cin >> input; input--; cache = vector<vector<long long>>(input, vector<long long>(10, 0)); long long answer = 0; for (int j = 1; j <= 9; j++) answer += check_stair(0, j, -1); cout << answer % MOD << endl; }

이 문제는 DP로 풀면 가능하다.

나는 cache를 앞의 index는 자리수 뒤의 index는 시작하는 숫자로 정했다.

즉 2번째 자리에 4로 시작하는 경우의 수를 알고싶으면 cache[2][4]로 가면 그 이후의 경우의 수가 모두 나오는 것이다.

그럼 시간을 빠르게 할 수있다. 예를 들어

3자리에서 시작수를 1로 하고 시작한다고 하자

1 2 1 / 1 2 3 이렇게 1 이후 2로 만들 수 있는 경우의 수는 2개이다.

이것을 저장해 놓는다. cache[2][2] = 2

그리고 이후 시작수를 3으로 놓을 때

3 2 1 / 3 2 3 이렇게 반복해서 찾을 필요없이

cache[2][2]를 이용해면 된다.