[BAE/<JOON> 문제풀이] 10844. 쉬운 계단수 (DP.010)

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

10844번: 쉬운 계단 수

소요시간 이틀에 걸쳐 약 17시간...

 

공책도 거진 10장은 쓴 것 같다...

 

머리가 나쁘면 몸이 고생한다.

 

자세한 해설은 나중에 시간이 남을 때 써야겠다. 

 

너무 힘들다..

 

#include <iostream>
#include <vector>

using namespace std;
int cnt = 0;
vector<int> arr;
vector<vector<unsigned long long>> ps;
vector<unsigned long long> ms;

void r(int n, int i) {
    if (n == i) {
        cnt++;
        return;
    }
    if (arr[i-1] > 0) {
        arr[i] = arr[i - 1] - 1;        
        r(n, i + 1);
    }
    if (arr[i-1] < 9) {
        arr[i] = arr[i - 1] + 1;
        r(n, i + 1);
    }
}

int main()
{
    /*int n = 20;
    for (int i = 1; i <= n; i++) {        
        cnt = 0;
        arr.resize(i + 1);
        for (int j = 1; j <= 9; j++) {
            arr[0] = j;
            r(i, 1);            
        }
        cout << cnt << endl;
    }*/

    int n;
    cin >> n;
    vector<vector<int>> arr;
    arr.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        arr[i].resize(11);          
    }

    for (int j = 1; j <= 9; j++) {
        arr[0][j] = 1;
    }

    arr[0][0] = 1;
    arr[0][9] = 1;
    for (int j = 1; j <= n; j++) {
        if (j % 2 == 0) {
            arr[j][0] = arr[j - 1][0] * 2 % 1000000000;
        }
        else {
            arr[j][0] = (arr[j - 1][0] + arr[j - 1][0] / (j / 2 + 1) * (j / 2)) % 1000000000;            
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 8; j++) {
            arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]) % 1000000000;
        }        
        arr[i][9] = arr[i - 1][8];
        arr[i][0] = arr[i - 1][1];
    }

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            printf("%d\t", arr[i][j]);
        }
        printf("\n");
    }

    int sum = 0;
    for (int i = 1; i <= 9; i++) {
        sum += arr[n-1][i];
        sum %= 1000000000;
    }

    cout << sum << endl;
    
    return 0;
}