[DP] BOJ - 10844번 (쉬운계단수)

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

10844번: 쉬운 계단 수

백준 DP 연습문제다.

끝 자리에 유의해서 DP[자리수][끝자리수]로 만들 수 있는 계단수를 찾으면 된다.

수가 매우 커지기 때문에 모듈러 연산을 위해 long long에 정답을 저장해야 하며,

동작과정 중 n을 만나면 계산해둔 값을 이용해 답을 출력한뒤 종료하도록 구현했다.

 

#include <stdio.h>
#pragma warning(disable:4996)
#define div 1000000000
int main(){
    long long DP[101][10];
    DP[1][0] = 0;
    for (int c = 1; c < 10; c++) DP[1][c] = 1;
    int n;
    scanf("%d", &n);
    if (n == 1){
        printf("9\n");
        return 0;
    }
    for (int r = 2; r <= 101; r++){
        for (int c = 0; c <= 9; c++){
            if (c == 0){
                DP[r][c] = DP[r - 1][1];
                DP[r][c] = DP[r][c] % div;
            }
            else if (c == 9){
                DP[r][c] = DP[r - 1][8];
                DP[r][c] = DP[r][c] % div;
            }
            else{
                DP[r][c] = DP[r - 1][c - 1] + DP[r - 1][c + 1];
                DP[r][c] = DP[r][c] % div;
            }
        }
        if (r == n){
            long long ret = 0;
            for (int c = 0; c <= 9; c++) {
                ret += DP[r][c]; // 모두 더한다음에 모듈러해준다.
            }
            printf("%lld\n", ret%div);
            break;
        }
    }
    return 0;
}