[백준 2798번] : 블랙잭

문제

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.
합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

브루트 포스 문제인 만큼 세 카드를 더할 수 있는 모든 경우의 수를 구하고 그중 M하고 제일 가까워지는 값을 구하면 된다.

시간 복잡도는 O(N^3) 이다.

#include <iostream>
#include <vector>


int main(void)
{
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	std::cin.sync_with_stdio(false);

	int N, M;
	std::cin >> N >> M;
	std::vector<int> cards(N, 0);

	for (int i = 0; i < N; i++)
		std::cin >> cards[i];

	int max = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (i == j)
				continue;
			for (int k = 0; k < N; k++)
			{
				if (j == k
					|| i == k)
					continue;

				int sum = cards[i] + cards[j] + cards[k];
				if (sum > M)
					continue;

				if (max < sum)
					max = sum;

			}
		}
	}

	std::cout << max << "\n";

	return 0;
}