백준 5557번 1학년 C++

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

5557번: 1학년

 

2차원 dp 배열을 만든다.

dp[i][j]는 i번째까지의 식의 결과가 j인 경우의 수이다.

 

처음에는 결과가 v[0] 하나만 존재하기 때문에 dp[0][v[0]] = 1로 초기값을 정해준다.

i가 늘어날때마다 j를 0~20을 검사하면서 dp[i-1][j]가 0이 아니라면 i-1번째까지의 값이 j인 경우가 존재한다는 뜻이다.

여기서 j+v[i], j-v[i]를 계산해 0~20사이라면 전 결과의 경우의 수만큼 더하면 되기 때문에 dp[i][계산한 값] += dp[i-1][j]이다.

 

최종적으로 계산된 값이 v[n-1]과 같아야 하기 때문에 dp[n-2][v[n-1]]을 출력한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
vector<int> v;
vector<vector<int64>> dp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    v = vector<int>(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    dp = vector<vector<int64>>(n, vector<int64>(21, 0));

    dp[0][v[0]] = 1;
    for (int i = 1; i < n - 1; i++) {
        for (int j = 0; j <= 20; j++) {
            if (dp[i - 1][j] == 0) continue;
            int val1 = j + v[i];
            int val2 = j - v[i];
            if (val1 <= 20) {
                dp[i][val1] += dp[i - 1][j];
            }
            if (val2 >= 0) {
                dp[i][val2] += dp[i - 1][j];
            }
        }
    }
    cout << dp[n - 2][v[n - 1]];
}