[BOJ] 10844 쉬운 계단 수

#include <stdio.h>

int memo[10][101];

int step(int n, int start)
{
    int ret = 0;

    if (n == 1)
        return 1;
    if (memo[start][n] != 0)
        return memo[start][n];

    if (start > 0)
        ret += step(n - 1, start - 1);
    ret %= 1000000000;
    if (start < 9)
        ret += step(n - 1, start + 1);

    memo[start][n] = ret % 1000000000;
    return memo[start][n];
}

int main(void)
{
    int i, n;
    int result = 0;

    scanf("%d", &n);
    for (i = 1; i < 10; i++) {
        result += step(n, i);
        result %= 1000000000;
    }
    printf("%d", result);

    return 0;
}

이 문제를 푸니까 메모이제이션을 활용하는 방법을 한 가지 더 알게된 기분이다.
이차원 배열로 메모이제이션을 하는게 계속 낯설었는데 이 문제는 잘 와닿는다. 연산 대상이 숫자라 그런 것 같다.
수학 문제도 식으로 써놓으면 그대로 풀 수 있는데 글로 풀어놓으면 그걸 식으로 변환하는 과정을 거쳐야하는 것처럼.
이런 문제에 익숙해지면 글로 쓰여있는 문제에서도 식을 찾아낼 수 있다.

오류는 두 가지.
배열 행을 9로 적고 index 9에 접근해서 스택 오버런이 나왔다.
다른 하나는 mod를 취하는 위치가 잘못되었던 것. 값이 더해지는 부분은 mod하지 않고 값을 구하는 부분만 해서 덧셈 시에 오버플로가 발생했다. 질문 검색으로 알았다.