백준[5557] 1학년

문제 설명

문제 링크

http://icpc.me/5557

5557번: 1학년

풀이

dp를 이용하여 해결할 수 있다.

dp[i][j] : j번째 숫자까지 봤을 때 숫자 i를 만들 수 있는 최댓값으로 정의할 수 있다.

코드

#include <cstdio>

using ll = long long;

ll dp[22][102], arr[102], n;

ll dpf(ll cur, ll idx) {
    if (cur < 0 || cur > 20) return 0;
    
    ll &ret = dp[cur][idx];
    if (ret) return ret;
    if (idx == n - 2) return cur == arr[n - 1];

    return ret += dpf(cur - arr[idx + 1], idx + 1) + dpf(cur + arr[idx + 1], idx + 1);
}

int main() {
    scanf("%lld", &n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", arr + i);
    }
    printf("%lld", dpf(arr[0], 0));
}