[백준] 10844 - 쉬운 계단 수, C++

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

10844번: 쉬운 계단 수

본 문제는 인접한 모든 자릿수의 차이가 1이 나는 수를 계단 수의 경우의 수를 구하는 문제다. 큰 문제를 작은 문제에서 구할 수 있기 때문에 DP로 풀 수 있다. i자리 수 중 j로 끝나는 경우의 수는 i-1자리 수 중 j+1, j-1의 경우의 수를 더한 값이다. 그러나 끝자리가 0인 경우는 1, 9인 경우는 8 밖에 없다. 따라서, 점화식을 d[i][j] = d[i-1][j+1] + d[i-1][j-1]로 정의하고, d[i][0] = d[i-1][1], d[i][9] = d[i-1][8]로 예외 처리를 하면 된다. (※ vacuous truth에 의해 1자리 계단로 쉬운 계단 수로 포함된다.)

1. 조건 중 1자리 수 중 0으로 시작하는 수는 없다.
2. 1자리 수를 1로 초기화
3. 마지막 수가 0, 9인 경우 예외 처리
4. d[i][j] = d[i-1][j-1] + d[i-1][j+1] 계산

문제에서 정답은 1,000,000,000으로 나머지 연산을 한 결과를 출력해야한다. 따라서 연산 결과를 mod 연산을 하면된다.

Top-down

#include <cstdio>
#include <cstring>
 
using namespace std;
 
long long d[101][10];
const long long Mod = 1000000000LL;
 
long long cal(int n, int i) {
    if(n == 1) {
        if (i == 0) return 0;
        else return 1;
    }
    if (d[n][i] != -1) return d[n][i];
    
    if (i == 0) d[n][i] = cal(n-1, 1) % Mod;
    else if (i == 9) d[n][i] = cal(n-1, 8) % Mod;
    else d[n][i] = (cal(n-1, i-1) + cal(n-1, i+1))%Mod;
    return d[n][i];
}
 
int main() {
    int n;
    scanf("%d", &n);
    long long ans = 0LL;
    memset(d, -1, sizeof(d));
    for (int i = 0; i <= 9; i++) {
        ans = (ans + cal(n, i))%Mod;
    }
    printf("%lld", ans);
}

 

Bottom-up

#include <cstdio>
 
using namespace std;
 
long long d[101][10];
const long long Mod = 1000000000LL;
 
int main() {
    int n;
    scanf("%d", &n);
    d[1][0] = 0;
    for (int i = 1; i <= 9; i++) {
        d[1][i] = 1;
    }
    for (int i = 2; i <= 100; i++) {
        d[i][0] = d[i-1][1] % Mod;
        d[i][9] = d[i-1][8] % Mod;
        for (int j = 1; j <= 8; j++) {
            d[i][j] = (d[i-1][j-1] + d[i-1][j+1]) % Mod;
        }
    }
    long long ans = 0;
    for (int i = 0; i <= 9; i++) {
        ans = (ans%Mod) + (d[n][i]%Mod);
    }
    printf("%lld", ans%Mod);
}