[백준 2798] 블랙잭

카드가 총 백장이므로 완전 탐색을 진행하여도  \(_{100}C_{3}\)개의 경우의 수 밖에 안나온다. 따라서 완탐으로 진행하자.완전 탐색하는 방법은 재귀 함수를 이용하면 되는데, 3개만 뽑으면 되기 때문에 3중 for문도 가능할 것으로 보인다.

 

1. 재귀 함수

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 1e5;
const int MOD = 1e9 + 3;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int n, m;
int cnt = 0, ans = 0;
int card[101];


void sum(int cur, int prev_sum, int cnt) {
	
	if (cnt == 3) {
		if (prev_sum <= m) ans = max(ans, prev_sum);

		return;
	}

	for (int i = cur; i < n; ++i) sum(i + 1, prev_sum + card[i], cnt + 1);

	return;
}

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

	cin >> n >> m;
	
	for (int i = 0; i < n; i++) cin >> card[i];

	sum(0, 0, 0);
	
    cout << ans;
}

2. 3중 for문

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 1e5;
const int MOD = 1e9 + 3;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int card[101];

int solve(int n, int m) {
	int ans = 0;

	for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) {
		if (card[i] + card[j] + card[k] == m) return m;
		else if(card[i] + card[j] + card[k] < m) ans = max(ans, card[i] + card[j] + card[k]);
	}

	return ans;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)cin >> card[i];

	cout << solve(n, m);
	return 0;
}