백준 2798 블랙잭

 

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

 

서론

 

재귀를 활용한 브루트포스

 

아이디어

 

주어진 수의 첫번째 숫자부터 마지막 숫자까지 재귀함수를 이용하여 완전탐색을 한다.

recursive(O/X){

 recursive(O);

 recursive(x);

}

 

 

 

5	6	7	8	9
O	O	O	X	X
O	O	X	O	X
O	O	X	X	O
O	X	O	O	X
O	X	O	X	O
O	X	X	O	O
X	O	O	O	X
X	O	O	X	O
X	O	X	O	O
X	X	O	O	O

 

탐색을 하던 중 O의 개수가 3개가 나오면 O를 모두 더해주고 M과 가장 가까운지 확인 후 리턴,

탐색깊이가 M과 같아지면 무한히 재귀에 빠지는것을 막기 위해 리턴

 

구현

 

//c++

#include <iostream>
#include <algorithm>

using namespace std;

int card[101];
int sum[4];
int n, m;
int dist = 999999;

void rec(int cnt, int cntTrue, int tf) { 
	if (cntTrue == 3) { 
		for (int i = 0; i < 3; i++) sum[3] += sum[i];
		if (sum[3] <= m) dist = min(dist, abs(sum[3] - m));
		sum[3] = 0;
		return; 
	}
	if (cnt == n) return;
	if (tf == 1) sum[cntTrue] = card[cnt];

	rec(cnt + 1, cntTrue + 1, 1);
	rec(cnt + 1, cntTrue, 0);

	return;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		card[i] = tmp;
	}
	rec(-1, -1, -1);
	cout << m - dist;
}