10844번 쉬운 계단 수

https://www.acmicpc.net/problem/10844

36번 째 줄을

ans += (dp[n][j] % Mod);

라고 써서, 틀렸다고 떴었다. ans을 더하면서 int 범위를 벗어나는 것 같다.

dp[i][j] = 길이가 i인 수에서 j로 끝나는 쉬운 계단 수

단, 끝이 0과 9일 때만 조심하면 된다.

길이가 i이고, 끝이 0일 때는 그 전 길이(i-1)에서는 끝이 1일 때만 계단 수가 된다.

길이가 i이고, 끝이 9일 때는 그 전 길이(i-1)에서는 끝이 8일 때만 계단 수가 된다.

#include <bits/stdc++.h>
 
using namespace std; 
 
#define Max 101
#define Mod 1000000000
 
int dp[Max][Max], n, ans;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }
 
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 0) {
                dp[i][j] += dp[i - 1][1] % Mod;
            }
            else if (j == 9) {
                dp[i][j] += dp[i - 1][8] % Mod;
            }
            else {
                dp[i][j] += (dp[i - 1][j - 1] % Mod + dp[i - 1][j + 1] % Mod) % Mod;
            }
        }
    }
    
    for (int j = 0; j <= 9; j++) {
        ans = (ans % Mod + dp[n][j] % Mod) % Mod;
    }
    
    printf("%d\n", ans % Mod);
 
    return 0;
}