백준 2798번 블랙잭

백준 2798번 블랙잭 문제는 브루트 포스 알고리즘으로 푸는 문제이다.

 

브루트 포스는 정말 간단한 알고리즘으로, 모든 경우의 수를 구해보고 해답을 찾는 알고리즘이라고 생각하면된다.

 

때문에 문제를 풀기에는 굉장히 쉽지만 경우의 수가 많아질수록 소요 시간이 기하급수적으로 올라갈 수 있다는 점이다.

 

2798번 문제는 N개의 정수가 주어지면, 그 중 3개의 정수를 합했을 때 M보다 작으면서 가장 큰 값을 구하는 문제이다.

 

이 문제는 3중 for문으로 반복하며 모든 경우의 수를 구하면서 주의해야할 점은 2, 3번째 for문의 index의 시작 범위를 잘 정해주어야한다는 점이다.

 

첫 번째 for 문의 index는 N - 2 전까지 돌고

두 번째 for 문의 index는 첫 번째 for 문의 index + 1 부터 N - 1전까지 돌고

세 번째 for 문의 index는 두 번째 for 문의 index + 1 부터 N까지 돌면 된다.

 

아래에 실행 코드가 있다.

#include <iostream>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	int* arr = new int[N];

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int max = 0;
	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++) {
				int sum = arr[i] + arr[j] + arr[k];
				if (sum > max && sum <= M)
					max = sum;
			}
		}
	}

	cout << max << endl;
	
	return 0;
}