[2798][BOJ] 블랙잭

문제

문제 출처

문제 해결 전략

브루트 포스 알고리즘을 이용해야 하기 때문에 모든 노드에 한 번씩 다 접근하는 방식을 이용해야만 했다. 선형 탐색을 이용했고 재귀로 문제를 구현했을 때 segmentation fault나 indexing 문제도 자주 일어나기 때문에 중첩 for loop을 세개를 사용해야 겠다는 생각을 했다. 초기에 그냥 오름차순 정리후에 뒤에서 부터 3개의 index를 선택하여 코드를 잤는데 ,, 쉬운 문제라고 생각하고 그렇게 구현한 내가 바보였다... 예외가 너무나도 많기 때문이다. 결국에 부르트 포스를 생각하고 그리디 알고리즘을 구현한 것이다.

코드

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

using namespace std;

int main(){
	int N, M;
	cin >> N >> M;
	int sum = 0;
	int i = 0;
	vector<int> card(N);
	vector<int> ans;
	for(int i = 0;i < N;i++) cin >> card[i];
		

	for(int i = 0;i < card.size();i++){
		for(int j = i+1;j < card.size();j++){
			for(int k = j+1;k < card.size();k++){
				if(card[i] + card[j] +card[k] <= M) ans.push_back(card[i]+card[j]+card[k]);
				else break;
			}
		}
	}
	cout << *max_element(ans.begin(), ans.end()) << endl;
}