[C++] 백준 2798번 블랙잭

브루트 포스 문제입니다.

카드 N개에서 3장을 골라 M을 넘지 않으면서 가장 근접한 숫자를 만들어야 합니다.

모든 카드에 대해서 3장을 뽑아 M과 가장 가까운 수를 찾아서 문제를 풀었습니다.
DFS방식을 통해 모든 경우의 수를 탐색했고,
M을 넘어갈 경우 return하는 방식으로 시간을 줄였습니다.

 

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
int minNum;
int nearNum;
int arr[110];

void DFS(int x, int c, int num)
{
	num += arr[x];

	if (m < num) {
		return;
	}

	if (c == 3) {
		if (minNum > m - num) {
			minNum = m - num;
			nearNum = num;
		}
		return;
	}

	for (int i = x + 1; i < n; ++i) {
		DFS(i, c + 1, num);
	}
}

int main(int argc, char *argv[])
{
	minNum = 987654321;
	nearNum = 987654321;
	cin >> n;
	cin >> m;

	memset(arr, 0, sizeof(arr));

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

	for (int i = 0; i < n - 2; ++i) {
		DFS(i, 1, 0);
	}

	cout << nearNum << endl;

	return 0;
}