백준 1562번 계단수

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

1562번: 계단 수

 

 DFS + DP 문제이다. DP를 사용하기 위해, 임의의 숫자로 시작하여 숫자를 하나씩 이어나갈 때 지금 몇 번째 숫자까지 붙였는지, 현재 숫자는 무엇인지, 0~9 숫자를 사용했는지 여부를 판단해야 한다. 근데 사실 0~9 까지의 숫자를 사용했는지 모두 확인할 필요가 없다. 0과 9라는 숫자만 사용되었다면 그 사이에 있는 숫자도 모두 사용되었을 수밖에 없다. 따라서 메모이제이션 배열을 cache 라 하면 cache[101][10][2][2] 이런 식으로 만들 수 있고, 101 은 dfs 의 깊이, 10 은 현재 숫자, 2는 각각 0과 9를 사용했는지 여부이다.

int n;
int cache[101][10][2][2];
const int DIV = 1000000000;

int dp(int cur, int curNumber, int zero, int nine) {
    if (curNumber == 0)
        zero = 1;
    if (curNumber == 9)
        nine = 1;

    if (cur == n) 
    	return zero && nine;

    int& ret = cache[cur][curNumber][zero][nine];
    if (ret != -1)
        return ret;

    ret = 0;
    if (cur == 0) {
        for (int i = 1; i < 10; ++i) {
            ret += dp(1, i, 0, 0);
            ret %= DIV;
        }
        return ret;
    }
    
    if (curNumber > 0) {
        ret += dp(cur + 1, curNumber - 1, zero, nine);
        ret %= DIV;
    }

    if (curNumber < 9) {
        ret += dp(cur + 1, curNumber + 1, zero, nine);
        ret %= DIV;
    }

    return ret;
}

int main() {
    cin >> n;
    memset(cache, -1, sizeof(cache));
    cout << dp(0, 0, 0, 0);

    return 0;
}