[백준알고리즘] 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)

 

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