[ boj : 5557 ] 1학년

www.acmicpc.net/problem/5557

5557번: 1학년

문제 : 수들이 주어지고 사이에 +,- 만 넣어서 맨 마지막 수를 만들 수 있는 경우의 수를 구하시오

 

해설 : 점화식만 잘 짤수 있으면 쉽게 풀 수 있는 문제입니다.

매번 나오는 중복된 수들을 일일이 세는 것이 아닌 메모를 해둔다면 빠른시간안에 해결 할 수 있겠죠.

dp[i][j] = 이전 단계까지 연산된 결과값에 j번째 수를 +,- 했을때 i 가 나올 수 있는 경우의 수

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll arr[100];
ll dp[21][100];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	dp[arr[0]][0] = 1;
	for(int i=1;i<n-1;i++)
		for(int j=0;j<=20;j++)
			if (dp[j][i - 1] > 0) {
				if (0<= j+arr[i] && j + arr[i] <= 20)
					dp[j + arr[i]][i] += dp[j][i - 1];
				if (0 <= j - arr[i] && j - arr[i] <= 20)
					dp[j - arr[i]][i] += dp[j][i - 1];
			}
	cout << dp[arr[n - 1]][n - 2];
	return 0;
}