백준 2798 블랙잭 [BruteForce]

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

2798번: 블랙잭

문제 풀이

카드의 합이 M을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만들면 됩니다.

카드가 1 ~ N장이 있을 때,

1번부터 카드를 시작해서 N번 카드로 갈 때,

해당 index 카드를 고를지 말지를 결정해서, picked의 수가 3개면 현재까지 구한 답과 비교해서 큰 값을 저장하면 됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, ans;

void solve(vector<int>& card, int idx, int picked, int sum)
{
	if (picked == 3)
	{
		if (sum <= M) ans = max(ans, sum);
		return;
	}

	if (idx >= card.size()) return;

	// 해당 idx 카드를 선택했다.
	solve(card, idx + 1, picked + 1, sum + card[idx]);
	// 해당 idx 카드를 선택하지 않았다.
	solve(card, idx + 1, picked, sum);
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> N >> M;
	vector<int> card(N);
	for (int i = 0; i < N; i++) cin >> card[i];
	solve(card, 0, 0, 0);
	cout << ans;
	return 0;
}

 

재귀함수로 풀지않고, 반복문으로도 해결할 수 있습니다.

내가 i번째 카드를 선택했다면, 그 다음 카드는 i+1부터 찾고, 그 다음 카드는 i+2부터 찾으면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	int ans = 0, sum = 0;
	for (int i = 0; i < N; i++)
		for(int j = i+1; j< N; j++)
			for (int k = j + 1; k < N; k++)
			{
				sum = card[i] + card[j] + card[k];
				if (sum <= M) ans = max(ans, sum);
			}

	cout << ans;
	return 0;
}