백준/2798/brute force/블랙잭

백준/2798/brute force/블랙잭

처음으로 풀어보는 알고리즘이다.
처음은 순서에 상관없이 전체적으로 배열을 탐색해야 된다는 생각에 조합 문제로 생각하여
조합과 비슷한 형태의 재귀형태로 문제를 풀었으나

for (int i = start; i < size; i++) {
		blackjack(arr, sum + arr[i], phase + 1, size, i + 1,maximum);
	}

이 부분에서 문제가 발견되었다.

1. 시간 초과
   phase를 이용해 탐색하는 범위를 줄였음에도 시간 초과가 발생하여 재귀 방법을 포기하고
   3중첩 for문을 이용함

풀이

1.첫 풀이

#include<iostream>
using namespace std;

int MAX = 0;

void blackjack(int* arr,int sum, int phase,int size,int start,int maximum) {
	if (sum > maximum) {
		return;
	}
	if (phase == 3) {
		if (MAX < sum) {
			MAX = sum;
			return;
		}
	}
	for (int i = start; i < size; i++) {
		blackjack(arr, sum + arr[i], phase + 1, size, i + 1,maximum);
	}
}

int main(void) {
	int M;
	int N;
	int* arr;
	cin >> N >> M;
	arr = new int[N];
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	blackjack(arr, 0, 0, N, 0, M);
	cout << MAX;
    delete []arr
}

2.두번째 풀이

#include<iostream>
using namespace std;

int main(void) {
	int arr[100] = { 0, };
	int N, M;
	cin >> N >> M;
	int MAX = 0;
	int sum=0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	for(int i=0;i<N-2;i++)
		for(int j=i+1;j<N-1;j++)
			for (int k = j + 1; k < N; k++) {
				sum = arr[i] + arr[j] + arr[k];
				if (sum > MAX && sum<=M)
					MAX = sum;
			}

	cout << MAX;
}