[PS 백준 - 2.2] 2798번: 블랙잭

문제 정보

백준 2798번 - 바로가기

• 난이도: 브론즈 2
• 알고리즘: 브루트포스 알고리즘

---

코멘트

브루트포스 알고리즘의 핵심은 for문으로 빠짐없이 노가다로 돌리기이다. 나는 각 숫자들을 3개씩 뽑아 sum이 M보다 작거나 같으면 result 벡터에 저장했고, 그 중에서 가장 큰 값을 구했다. 이 문제도 역시 $_{N}\mathrm{C}_{3}$ 의 모든 경우를 다 탐색했다.

---

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int n, m, temp;
	cin >> n >> m;

	vector<int> vec;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}

	sort(vec.begin(), vec.end());
	
	int sum = 0;
	int ansI = 0, ansJ = 0;

	vector<int> result;

	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			for (int k = j+1; k < n; k++) {
				sum += vec[i] + vec[j] + vec[k];
				if (sum <= m) {
					result.push_back(sum);
				}
				sum = 0;
			}
		}
	}
	
	sort(result.begin(), result.end());

	cout << result[result.size()-1];
}