백준 5557 1학년

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

5557번: 1학년

 

다이나믹 프로그래밍.

 

중요한 건 시작할 때 (0,0)으로 시작하면 안된다는 점이다.

 

이럴 경우

4

0 0 0 0

 

같은 반례에 걸린다. 무조건 첫 값을 지정해줘야한다. 

 

/* 1학년 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>


#define ll long long int

using namespace std;

void input();
void solve();

int N;
ll dp[101][21];
vector<int> arr;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input(); solve();
	return 0;
}

void input() {
	cin >> N;
	arr.resize(N);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; i++)
		cin >> arr[i];
}

ll b_t(int idx, ll summation) {
	if (summation > 20 || summation < 0)
		return 0;

	if (idx == N - 1) {
		if (summation == arr[idx])
			return 1;
		return 0;
	}

	ll& res = dp[idx][summation];
	if (res != -1) {
		return res;
	}

	return res = b_t(idx + 1, summation + arr[idx]) + b_t(idx + 1, summation - arr[idx]);
}

void solve() {
//무조건 1, arr[0]으로 시작해야한다.
	cout << b_t(1, arr[0]) << '\n';
	return;
}