[백준 2798] 블랙잭

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

2798번: 블랙잭

 

요구사항

1. 카드 3개 골랏을때 M을 넘지않으며 M과 가장 가까운 값 고르기

 

풀이

요구사항을 기저사례로 하여 재귀함수를 사용하면 된다

1. 카드 3개 이상

2. M 넘었을 경우

3. 카드 3개인데 합이 제일 가까울때

 

#include <iostream>

using namespace std;

int n, m;
int map[101];
int ans = 0;
void solve(int nownum, int nowidx, int cnt, int sum)
{
	if(sum>m)
		return;
	if (cnt > 3)
		return;
	if (cnt == 3)
	{
		if (ans < sum)
			ans = sum;
		return;
	}

	for (int i = nowidx + 1; i < n; i++)
	{
		solve(map[i], i, cnt + 1, sum + map[i]);
	}
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> map[i];
	}
	for (int i = 0; i < n; i++)
	{
		solve(map[i],i, 1, map[i]);
	}
	cout << ans << endl;
}