[백준] 5557번 - 1학년 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic Programming) - 1학년

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

5557번: 1학년

 

F (Idx, PartialSum) : 0번째 수부터 Idx까지의 합의 개수

DP에 적용할 점화식을 다음과 같다고 하자. 그럼 점화식을 F(Idx + 1, PartialSum + number[Idx + 1])  + F(Idx + 1, PartialSum - number[Idx + 1])로 통해 올바른 등식의 개수를 구할 수 있다.

 

 

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 103
	#define MOD 1000000000
	#define int ll
	using namespace std;
	typedef pair<int, int> p;
	int n;
	int numbers[MAX];
	int cache[MAX][21];
	int solve(int idx, int total) {
	if (total < 0 || total > 20)return 0;
	if (idx == n - 2 && total == numbers[n - 1]) return 1;
	int& ret = cache[idx][total];
	if (ret != -1) return ret;
	ret = 0;
	return ret += (solve(idx + 1, total + numbers[idx + 1]) + solve(idx + 1, total - numbers[idx + 1]));
	}
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i)
	cin >> numbers[i];
	memset(cache, -1, sizeof(cache));
	cout << solve(0, numbers[0]) << endl;
	return 0;
	}

view raw 5557.cpp hosted with ❤ by GitHub