#include <stdio.h> #define mod 1000000000 int main(void) { int N; int Dp[101][10] = {}; int sum = 0; scanf("%d", &N); for (int i = 0; i < 10; i++) Dp[1][i] = 1; for (int i = 2; i <= N; i++) { for (int j = 0; j < 10; j++) { if (j == 0) Dp[i][0] = Dp[i - 1][1] % mod; else if (j == 9) Dp[i][9] = Dp[i - 1][8] % mod; else Dp[i][j] = (Dp[i - 1][j - 1] + Dp[i - 1][j + 1]) % mod; } } for (int i = 1; i < 10; i++) sum = (sum + Dp[N][i]) % mod; printf("%d\n", sum%mod); }
|
쉬운 계단수라고 하는데, 왜 이것을 정확하게 풀어내지 못하는 것이지. 접근 아이디어는 동일합니다. 디피로 풀고, 0과 9일때가 문제이기 때문에 이것에 대해서 처리하면 됩니다. 그리고 디피문제의 공통점은 0이나 1,2 까지느 직접 너어주고 다음부터는 자동으로 계산하도록 처리합니다. |
그런데 뒷자리 숫자에 대해서는 인덱스를 만들 생각을 하지 않았습니다. 이게 차이점이고, 더욱 적어도 1,2,3 까지 만들어서 이것에 대한 예제를 만들면 좋았겠다는 생각을 합니다. 그리고 0과 9 일때의 예외처리에 대해서 알았으므로, 2와8까지만 규칙을 찾고 그 아래에 대해서는 찾지않아도 무방하다는 것을 캐치합니다. |