백준 5557번: 1학년

[문제 링크]

5557번: 1학년

---

간단한 dp 문제였다.

현재 계산하려는 위치와, 누적한 값에 따른 올바른 등식의 개수를 2차원 dp배열에 저장하여 중복을 최소화하였다.

---

#include <iostream>
#include <cstring>
using namespace std;

int N, arr[101];
long long memo[101][21];

long long Topdown(int here, int sum)
{
	if (sum < 0 || sum > 20) return 0;
	if (here == N) return sum == arr[N] ? 1 : 0;

	long long& ret = memo[here][sum];
	if (ret != -1) return ret;

	ret = 0;

	ret += Topdown(here + 1, sum + arr[here]);
	ret += Topdown(here + 1, sum - arr[here]);

	return ret;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	cin >> N;

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

	cout << Topdown(2, arr[1]) << endl;

	return 0;
}

 

알고리즘 200일 프로젝트 - 99 day