백준(BOJ) 1495 기타리스트 **

# DP

#include <iostream>
using namespace std;
int n,m,s,f,dp[105][1005];
int main(void)
{
	scanf("%d%d%d", &n, &s, &f);
	dp[0][s] = 1;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &m);
		for (int k = 0; k <= f; k++)
			if (dp[i][k] == 1)
			{
				if (0 <= k + m&&k + m <= f)
					dp[i + 1][k + m] = 1;
				if (0 <= k - m&&k - m <= f)
					dp[i + 1][k - m] = 1;
			}
	}
	m = -1;
	for (int i = f; 0<=i; i--)
		if (dp[n][i] == 1)
		{
			m = i;
			break;
		}
	printf("%d", m);
	return 0;
}