[백준 5557] 1학년, C++

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

5557번: 1학년

 본 문제는 0 ~ 20 중에서 n개를 선택하여 1 ~ (n-1) 사이에 +, -를 대입하여 계산하였을 때 결과가 n인 경우의 수를 구하는 문제다. (경우의 수는 2^63-1 이하) 이때, 1 - 3 + 4 = 2에서 계산을 하면서 음수가 되는 경우와(-2 + 4 = 2)는 제외한다. 20 + 20 - 20 = 20에서 계산을 하면서 20을 넘는 경우(40 - 20 = 20)는 제외한다. 그림으로 문제를 다시 설명하면 다음과 같다.

이때, j, j - v[i]는 20을 넘지 않는 양수이며 v[i]는 □의 수를 뜻한다. 그림을 점화식으로 정의하면 d[i][j] = d[i-1][j-v[i]] + d[i-1][j+v[i]]로 표현할 수 있다.

#include <cstdio>
#include <vector>
#include <cstring>
 
using namespace std;
 
long long d[101][21];
 
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    memset(d, 0, sizeof(d));
    d[1][v[1]] = 1;
    for (int i = 2; i < n; i++) {
        for (int j = 0; j <= 20; j++) {
            if (j-v[i] >= 0) d[i][j] += d[i-1][j-v[i]];
            if (j+v[i] <= 20) d[i][j] += d[i-1][j+v[i]];
        }
    }
    printf("%lld\n", d[n-1][v.back()]);
}