[2798] 블랙잭

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

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

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

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

예제 입력

5 21 5 6 7 8 9

예제 출력

21

 

---

문제풀이  

완전 탐색 문제를 풀고 싶어서 백준에서 찾아본 문제다.

n개의 카드중에서 3개의 카드를 뽑아 그 합이 m에 가장 근접하면 된다.

주어진 카드 중 하나를 먼저 선택하고 나머지 2개를 재귀 호출을 이용해 구한다 

1. 주어진 카드들 - cards

2. 총 합 - sum

3. 몇 개째 카드를 선택했는지 - cnt

아직 답의 수의 상한까지는 구하지 못했지만 다른 블로그를 살펴보니 완전 탐색으로도 풀리는 문제였다.

사실 이렇게 풀지 않고 다른 방법으로 풀었으나 자꾸 백준에서 틀렸다고 나와서 내 코드가 내가 모르는 문제가 있구나 하고 바로 날려버렸다. 그래서 밑의 코드는 https://jaimemin.tistory.com/856 님의 코드를 거의 배낀 코드이다.

/* n장에 카드중에서 m에 가장 가까운 카드 3장의 합을 출력 */
/* 2019-07-09 블랙젝 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;
int result;
vector<int> cards;

void pick(int idx, int cnt, int sum) {
	if (cnt == 3 && sum <= m)
	{
		result = max(result, sum);
		return;
	}

	if (idx >= n || cnt > 3 || sum > m) return;

	pick(idx + 1, cnt + 1, sum + cards[idx]);
	pick(idx + 1, cnt, sum);
}

int main() {
	int temp;
	cin >> n >> m;

	cards.resize(n);
	for (int i = 0; i < n; i++) { cin >> cards[i]; }
	sort(cards.begin(), cards.end(), greater<int>()); // 내림차순 정렬
	pick(0, 0, 0);

	cout << result;
}

 

사실 빠르게 찾고 싶어서 벡터를 내림차순 정렬을 해서 찾는 방법을 선택했지만 이 문제에선 그럴 필요까진 없어보인다.

pick 함수에서는 카드를 뽑고 제거한다. 먼저 3장의 카드를 다 뽑고 sum이 제시 된 m보다 작다면 result의 값을 바꿔준다. 이때 m보다 작은 경우의 수는 다양하지만 우리는 가장 근접한 결과를 얻고 싶은 것이기 때문에 result의 값을 저장하고 max 함수를 이용해 다시 구한 sum과의 대소 비교를 한다.

벡터를 순회하는 과정에서 idx가 범위를 벗어나거나 3장 이상의 카드를 뽑았거나 sum이 m보다 크다면 탐색을 즉시 중단한다.

위의 두가지 경우가 아니라면 재귀 탐색을 통해 벡터의 다음 idx를 탐색하는데 이때 한장의 카드를 이미 뽑았다는 뜻이므로 cnt도 증가하고 sum도 증가해서 구한다. 

두번째 if문에 걸리지 않는다면 3장의 카드를 뽑고 그 sum의 m을 넘지 않을때까지 계속 pick함수에 들어가게 된다. 우리는 모든 경우의 수를 탐색하기 때문에 뽑은 카드를 제거 해 주는 과정이 필요하다. 그게 바로 그 다음 코드다.

---

 

사실 아직 완벽하게 이해를 못해서 잘 모르겠다. 완전 탐색을 좀 더 열심히 공부해보고 다시 한번 풀어봐야겠다.