5557 1학년

#include <iostream>
#include <cstring>

using namespace std;

int N;
int numbers[101] {};
long long memo[101][21];

long long equations(int depth, int num)
{
    if (depth < 0 || num < 0 || num > 20) {
        return 0;
    }
    if (depth == 1 && num == numbers[1]) {
        return 1;
    }
    if (memo[depth][num] != -1LL) {
        return memo[depth][num];
    }

    memo[depth][num] = equations(depth - 1, num - numbers[depth]) + equations(depth - 1, num + numbers[depth]);

    return memo[depth][num];
}

void solve()
{
    long long ans = equations(N - 1, numbers[N]);
    cout << ans << endl;
}

void input()
{
    cin >> N;
    memset(memo, -1LL, sizeof(memo));
    for (int i = 1; i <= N; i++) {
        cin >> numbers[i];
    }
}

int main(void)
{
    input();
    solve();

    return 0;
}

처음엔 dfs로 해결하려고 했지만 너무 복잡해져서 다른 방법을 생각했다.

어짜피 각 자리수 까지의 연산 결과만 필요한거니 memo배열에 저장해놓고 이후 동일한 계산을 반복하지 않게 했다.

음수가 나오면 케이스는 종료된다. 그래서 아예 맨 처음에 각 자릿수까지의 연산 결과를 -1로 초기화했다.