백준[10844] - 쉬운계단수

문제

백준 10844 문제 보기

접근 방법

바로 앞의 수가 0과 9일때 주의해서 점화식을 세운다. 처음 제출할 때 출력할때만 나머지를 계산해서 출력되도록해서 오버플로우 발생으로 오답이 됐다.
점화식은 자릿수와 바로 앞의 숫자를 인덱스로 모든 경우를 저장한다.
if(앞에 저장된 숫자가 0) dp[i][j] = dp[i - 1][1];
if(앞에 저장된 숫자가 9) dp[i][j] = dp[i - 1][8];
나머지 모든 경우는 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

코드

#include <iostream>
 
#define mod 1000000000
 
using namespace std;
 
int N;
long long dp[101][10];
 
int main() {
 
    cin >> N;
 
    dp[1][0] = 0;
    for(int i = 1; i <= 9; i ++) {
        dp[1][i] = 1;
    }
 
    for(int i = 2; i <= N; i ++) {
        for(int j = 0; j <= 9; j ++) {
            dp[i][j] = 0;
 
            if(j == 0) {
                dp[i][j] = dp[i - 1][1];
            } else if(j == 9) {
                dp[i][j] = dp[i - 1][8];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
 
            // 숫자가 너무 커서 오버플로우, 미리 나눈값 저장.
            dp[i][j] %= mod;
        }
    }
 
    long long ans = 0;
    for(int i = 0; i <= 9; i ++) ans += dp[N][i];
 
    cout << ans % mod << endl;
    return 0;
}