백준 5557 c++

DP[N][21]으로 만들어 저장한 숫자 N개를 20을 넘지 않는 한에서 순회를 돌릴 수 있음.
입력된 숫자들에 대해 순회를 돌리는데 마지막 숫자는 동일하게 맞춰야 하는 숫자니까 제외함.

for (i = 1; i < N - 1; i++) {//마지막 숫자 제외
	for (j = 0; j <= 20; j++) { // 계산 결과값을 인덱스로 순회
		if (DP[i - 1][j] > 0) { // 이전 단계의 결과값이 유효할 때만 계산//DP의 값으로 경우의 수가 들어가니까 값이 0이면 해당 값을 만들 수 있는 경우의 수가 없다는 뜻
			if (j + numbers[i] <= 20) {//덧셈의 경우
				DP[i][j + numbers[i]] += DP[i - 1][j];//이전 계산의 경우의 수 더하기
			}
			if (j - numbers[i] >= 0) {//뺄셈의 경우
				DP[i][j - numbers[i]] += DP[i - 1][j];//이전 계산의 경우의 수 더하기
			}
		}
	}
}

#include <iostream>
#include <vector>

using namespace std;

void input_numbers(vector<int>& numbers) {
	cout << "input_numbers()\n";
	int i, N, num;

	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> num;
		numbers.push_back(num);
	}

	return;
}

long long find_answer(vector<int>& numbers) {
	cout << "find_answer()\n";
	
	long long answer = 0;
	int N = numbers.size();
	vector<vector<long long>> DP(N, vector<long long>(21, 0));
	int i, j;

	//상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 
	//따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 
	//예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

	DP[0][numbers[0]] = 1;//첫 숫자는 + 연산으로 고정
	for (i = 1; i < N - 1; i++) {//마지막 숫자 제외
		for (j = 0; j <= 20; j++) {
			if (DP[i - 1][j] > 0) { // 이전 단계의 결과값이 유효할 때만 계산
				if (j + numbers[i] <= 20) {
					DP[i][j + numbers[i]] += DP[i - 1][j];
				}
				if (j - numbers[i] >= 0) {
					DP[i][j - numbers[i]] += DP[i - 1][j];
				}
			}

			cout << DP[i][j] << " ";
		}
		cout << "\n";
	}
	answer = DP[N - 2][numbers[N -1]];

	return answer;
}

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

	vector<int> numbers;

	input_numbers(numbers);
	cout << find_answer(numbers) << "\n";


	return 0;
}