[백준 / C++] 5557 - 1학년

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

5557번: 1학년

다음 수를 더하고 빼는 경우의 수를 계속 세나가야 하는 DP 문제이다. dp[i][j]는 i번째 수까지 계산에 넣었을 때 그 합이 j가 되는 경우의 수이다. n번째 수를 계산에 넣기 전에 dp[n-1]를 0부터 20까지 돌려 n번째 수를 더하거나 뺐을 떄 0 이상 20 이하이면 경우의 수를 더해주면 된다.

#include <iostream>
#define MAX 101
using namespace std;

long long dp[MAX][21] = {0};
int arr[MAX];
int n;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    dp[1][arr[1]]++;
    for (int i = 2; i < n; i++) {
        for (int j = 0; j <= 20; j++) {
            if (dp[i - 1][j]) {
                if (j + arr[i] <= 20)
                    dp[i][j + arr[i]] += dp[i - 1][j];
                if (j - arr[i] >= 0)
                    dp[i][j - arr[i]] += dp[i - 1][j];
            }
        }
    }

    cout << dp[n - 1][arr[n]] << "\n";
    return 0;
}