[백준] 2798 블랙잭

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

2798번: 블랙잭

---

브루트 알고리즘을 활용하는 문제이다. 즉, 모든 경우의 수를 살펴보고 답을 구하는 것이다. 

 

변수 ret에는 M과 3개의 숫자를 선택했을 때의 합과의 차이를 저장한다. 문제에서 3개의 원소의 합이 M을 넘어가면 안된다고 했으므로, M보다 작을 경우에만 저장하면된다. 또한 M과 세개의 수의 합의 차가 가장 작아야하므로, ret가 더 작은 경우가 발생할 경우 값을 업데이트한다. 

 

마지막으로 출력값을 M에서 차이 값만큼 빼주면 된다. 

 

(아무런 형식이 지켜지지 않아 정신 없는 코드이지만, 블로를 정리해가면서 차차 나아지지 않을까라는 기대를 가지고 있다... 코드만 봐도 많은 도움이 필요함을 알 수 있을 것이다. 다양한 피드백을 언제나 환영합니다! 또한 기존 블로거들은 흠잡을 곳이 없어 현타가 왔겠지만, 많은 알고리즘 비기너들이 내 블로그를 읽으며 위안을 얻고 힘차게 나아갔을 좋겠다 ㅎㅎㅎ

힘든 싸움 함께 나아가봐요 ㅜㅜ)

---

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
int M;
int ret = 9876550;
//브루트 포스(Brute Force 알고리즘)
// 완전 탐색 알고리즘이다. 때문에 모든 수를 모두 탐색하면서 요구조건에 충족되는 결과를 가져와야함.
void solve(int i) {
	int sum = v[i];
	for (int k = i+1; k < v.size()-1; k++) {
		for (int j = k + 1; j < v.size(); j++) {
			sum += (v[k] + v[j]);
			if (M-sum < ret && M-sum >=0) {
				ret = M-sum;
				
			}
			sum = v[i];
		}	
	}
}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(); cin.tie();
	int N;
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		int a;
		cin >> a;
		v.push_back(a);
	
	}
	
	for (int i = 0; i < N - 2; i++) {
		solve(i);
	
	}
	
	cout << M - ret;

}