백준 5557번 1학년 C/C++ 풀이

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

 

DP 문제.

해당 idx에 어떤 sum을 가지고 있는가를 저장해나가며 함수를 진행시켜나간다.

 

계산 중간에 0~20을 넘어가는 경우 더이상 진행하지 않기 때문에 이를 저장하지 않는다.

 

#include <stdio.h>
#include <memory.h>

#define MAX 101

FILE* in = fopen("input.txt", "r");

int n;
int array[MAX];
long long int cnt;
long long int cache[MAX][21];
int dst;

//재귀로 구현한 dp
long long int dp(int idx, int sum) {
	//계산 값이 범위를 벗어나는 경우 return
	if (sum < 0 || sum > 20)
		return 0;
    //메모이제이션 사용
	if (cache[idx][sum] != -1)
		return cache[idx][sum];
    //n-2일 때 값이 원하는 값이면 1 아니라면 0 return
	if (idx == n - 2)
	{
		if (sum == dst)
			return 1;
		else
			return 0;
	}

	long long val = 0;

	//return값 val은 idx n-2까지의 합이 array[n-1]인 것
	val += dp(idx + 1, sum + array[idx + 1]);
	val += dp(idx + 1, sum - array[idx + 1]);

	return cache[idx][sum] = val;
}

int main() {
	fscanf(in, "%d", &n);
	for (int i = 0; i < n; i++)
		fscanf(in, "%d", &array[i]);
	dst = array[n - 1];
	memset(cache, -1, sizeof(cache));
	printf("%lld", dp(0, array[0]));
}