백준 10844: 쉬운 계단 수(DP)

#include <iostream>
 
unsigned int dp[101][10];
 
int main()
{
    int N = 0;
    std::cin >> N;
    for (int i = 1; i <= 9; ++i)
        dp[1][i] = 1;
    for (int i = 2; i <= N; ++i)
        for (int j = 0; j < 10; ++j)
        {
            if (j == 0)
                dp[i][j] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
        }
    unsigned long long ans = 0;
    for (int i = 0; i < 10; ++i)
        ans += dp[N][i];
    std::cout << ans % 1000000000;
    return 0;
}

십억을 중간과정에서 나머지연산하면 오버플로는 막겠지만 값이 변하지 않나..

하... 모르겠다...

그냥 전체적으로 조졌다... 왜 일케 하는지는 알겠는데 내가 직접 로직을 세우지도 못했고... 아직도 나머지연산은 이해가 안대고... DP빡고수라고 자화자찬 하자마자 개뚜드려맞았다...