[백준] 2798 블랙잭

문제링크] https://www.acmicpc.net/problem/2798

2798번: 블랙잭

---

문제요약

N개의 숫자가 주어졌을 때 3장의 숫자를 골라 모두 더하였을 때, 그 값이 M을 넘지 않고 M과 가장 가까운 값을 구하는 문제입니다.

풀이

브루트 포스 알고르즘 문제입니다. 모든 경우의 수를 계산하여 M에 가까운 값을 찾는 알고리즘을 구현하면 됩니다. 이 알고리즘의 경우에는 for문이 3번이 중첩 되어서 시간복잡도가 O(N^3) 으로 매우 크지만 문제의 조건에서 N이 100이하이기 때문에 최악의 경우 10^6 번의 반복이 이루어집니다. 10^6은 컴퓨터가 계산하기에 매우 큰 수는 아니므로 알고리즘을 푸는데 큰 지장은 없습니다. 

 

코드는 c/c++로 작성되었습니다.

#include <iostream>

using namespace std;

int arr[101];

int blackJeck(int arr[], int num, int max) {
	int result = 0;
	for (int i = 0; i < num-2; i++) {
		for (int j = i+1; j < num-1; j++) {
			for (int k = j+1; k < num; k++) {
				if ((arr[i] + arr[j] + arr[k] > result) && (arr[i] + arr[j] + arr[k] <= max)) result = arr[i] + arr[j] + arr[k];
				if (result == max) return result;
			}
		}
	}
	return result;
}

int main() {
	int num, max;
	cin >> num;
	cin >> max;

	for (int i = 0; i < num; i++) {
		cin >> arr[i];
	}

	cout << blackJeck(arr, num, max);
	

	return 0;
}