알고리즘/BOJ

백준 5557번: 1학년

대 혁 2020. 7. 14. 01:22

[문제 링크]

 

5557번: 1학년

문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들��

www.acmicpc.net


간단한 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