온라인 초등학생

초등학생

수학 덧셈 뺄샘

뺄셈이 음수의 덧셈  

앤개의 수가 있고, 앞에 있는 앤-1 개의 수 사이에 + - 마지막 수가 나오게 하는 경우의 수

마지막 두 수 사이에는 = 가 들어감

처음 엔-1 개의 수 사이에는 + - 가 들어간다고 생각하면 됨

연산은 초등학생이 하는 것이기 때문에, 계산 도중 음수나, 20을 초과하는 수가 등장하면 안됨

#include <iostream>

using namespace std;

#define MOD 1234567891
#define ll long long
#define MAX_N 101
#define MAX_SUM 21

int N;
ll input[MAX_N];
ll cache[MAX_N][MAX_SUM];   // cache[i][sum] = i번째 인덱스까지의 누적합이 sum인 경우의 수.
ll recursive_cnt;
int dest;

void init(void)
{
    dest = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < MAX_SUM; j++) {
            cache[i][j] = -1; // 초기화
        }
    }
    recursive_cnt = 0;
}

ll solve(int digit, int sum)
{
    if (sum < 0 || sum > 20)
        return 0;

    ll &ret = cache[digit][sum];

    if (digit == N - 2) {
        ret = (sum == dest) ? 1 : 0;
        return ret;
    }

    if (ret != -1)
        return ret;

    ret = 0;

    int next = digit + 1;
    ret = (ret + solve(next, sum - input[next])) % MOD;
    ret = (ret + solve(next, sum + input[next])) % MOD;
    return ret;
}

int main(void)
{
    freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    for (int tc = 1; tc <= T; tc++) {
        cin >> N;
        init();

        for (int i = 0; i < N - 1; i++)
            cin >> input[i];
        cin >> dest;

        solve(0, input[0]);
        cout << "#" << tc << " " << cache[0][input[0]] << endl;
    }
    return 0;
}

- mod, long long
- input
- cache
- recursive
- recursive 사용하는데, 사용하는 이유