문제 풀이

idx가 n-2까지 도착했을때 val이 n-1번째 피연산자 값과 같다면 그 등식은 올바른 등식이므로 return 1을해주고 아니면 0을 해준다.

val이 20이 넘어가거나 음수가 나올경우는 성립하지 않으므로 0을 반환한다.

idx번째에서 계산 값이 val일때 올바른 등식의 개수를 세기 위해
$dp[idx][val] += solve(idx + 1, val + arr[idx + 1]) + solve(idx + 1, val - arr[idx + 1]);$를 수행한다.

문제 링크

boj/5557

소스코드

PS/5557.cpp

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<memory.h>
#include<queue>
using namespace std;

long long dp[101][21];
int arr[101];
int n;
long long solve(int idx, int val);
int main(void)
{

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	memset(dp, -1, sizeof(dp));

	cout << solve(0, arr[0]);

}

long long solve(int idx, int val)
{

	if (val > 20 || val < 0)
		return 0;
	if (idx == n - 2)
		return (arr[n - 1] == val);
	if (dp[idx][val] != -1)
		return dp[idx][val];
	dp[idx][val] = 0;
	dp[idx][val] += solve(idx + 1, val + arr[idx + 1]) + solve(idx + 1, val - arr[idx + 1]);
	return dp[idx][val];
}