[백준알고리즘] 2798번: 블랙잭 -Python, C++

[백준알고리즘] 2798번: 블랙잭 -Python, C++

2798번: 블랙잭 (acmicpc.net)

2798번: 블랙잭

저번에도 파이썬으로 풀었던 문제인데, 파이썬은 먼저 조합을 모두 구한 뒤 적절한 답을 찾았다면, 이번에 푼 C++은 약간 다르게 풀었다.

 

BFS와 비슷하게 풀었으며, \(Queue\)를 사용했다. \(Queue\) 안에는 tuple을 사용해서 세 개의 값을 쌍으로 단위 처리했다.

tuple 안에는 (카드 선택 횟수, 현재까지 선택한 카드의 합, 가리키는 카드의 인덱스)로 구성되어 있다.

 

카드가 세 개 선택되었으면 \(max\_val\) 인지 확인해서 값을 변경해주기 위해 삼항 연산자를 사용했다. 

그리고 카드가 세 개 선택된 상태가 아니라면 \(Queue\)에서 하나 씩 뽑아내어서 다음 index의 카드를 포함시키는 경우와 포함시키지 않는 경우를 모두 \(Queue\)에 다시 넣어준다.

 

그러다 보니 카드를 정렬을 해놓음으로써 다음 카드를 선택할 경우 목표 값인 \(m\) 보다 크게 되면 \(Queue\)에 넣지 않게 하기 위해 카드들을 오름차순으로 정렬해주었다.

정렬하는 것은 <algorithm> 헤더의 sort를 사용했으며, int 배열이기 때문에 iterator를 호출하는 begin과 end가 없기 때문에 포인터의 시작 위치와 포인터가 끝난 다음 위치(포인터가 끝나는 위치는 cards[n-1]로 cards[n]은 포함되지 않음)를 넣어주었다.

 

---

아래는 C++ 코드다.

#include <iostream>
#include <algorithm>
#include <queue>

void solve(void);

int main(void)
{
	solve();
}

int find_answer(int*& cards, int size, int target)
{
	std::queue<std::tuple<int, int, int>> q; // count, sum, idx
	q.push(std::make_tuple(0, 0, -1));

	int max_val = 0;
	while (q.size())
	{
		int c, s, i;
		std::tie(c, s, i) = q.front(); q.pop();

		if (3 == c)
		{
			max_val = (max_val < s) ? s : max_val;
			continue;
		}

		i++;
		if (size == i) continue;
		q.push(std::make_tuple(c, s, i));

		s += cards[i];
		if (target < s) continue;
		if (target == s && size == c + 1) return s;
		q.push(std::make_tuple(c + 1, s, i));
	}

	return max_val;
}

void solve(void)
{
	int n, m;
	std::cin >> n >> m;

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

	std::sort(cards, cards + n);

	int answer = find_answer(cards, n, m);

	delete[] cards;
	std::cout << answer;
}

 

---

 

아래는 파이썬 코드로, itertools의 combinations를 사용해 선택 가능한 카드 조합을 모두 찾았다. 

각 조합별 합을 구해 \(m\)보다 작거나 같으면서 가장 큰 값을 선택했다.

from itertools import combinations

n, m = map(int, input().split())
# n개의 숫자들 중에서 3개를 선택해서
# m을 넘지않으며 m에 가장 가까운 조합을 만들어야함

card = list(map(int, input().split()))
ans = 0

for tmp in combinations(card, 3):
    if ans == m:
        break
    elif sum(tmp) > ans and sum(tmp) <= m:
        ans = sum(tmp)

print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다