(c++)백준 5557번: 1학년

www.acmicpc.net/problem/5557

5557번: 1학년

[풀이]

DP로 풀 수 있는 문제였다.

DP[i][j] : i번째 숫자차례에서 덧셈 혹은 뺄셈한 결과가 j인 경우의 수

점화식

DP[i][j+Num[i]] += DP[i-1][j]

DP[i][j-Num[i]] += DP[i-1][j]

 

#include <iostream>
using namespace std;

int N;
int Num[101];
long long DP[101][21] = { 0, };

void solution() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 20; j++) {
			if (j + Num[i] <= 20)
				DP[i][j + Num[i]] += DP[i - 1][j];
			if (j - Num[i] >= 0)
				DP[i][j - Num[i]] += DP[i - 1][j];
		}
	}
	cout << DP[N-1][Num[N]] << '\n';
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> Num[i];
	}
	DP[1][Num[1]] = 1;
	solution();
	return 0;
}