[백준 2798] 블랙잭

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

💻 문제 풀이 : C++

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> v_card;
vector<int> selected;
int used[101];
int answer;

int my_max(int a, int b)
{
	return a > b ? a : b;
}

void dfs(int depth, int start)
{
	if (depth >= 3) {
		int sum = 0;
		for (int i = 0; i < size(selected); i++)
		{
			sum += selected[i];
		}
		if (sum > M) return;

		answer = my_max(answer, sum);

		return;
	}
	
	for (int i = start ; i < N; i++) {
		if (used[i] == 1) continue;
		used[i] = 1;
		selected.push_back(v_card[i]);
		// dfs(depth + 1, start + 1);
		dfs(depth + 1, i);
		used[i] = 0;
		selected.pop_back();
	}
}

int main()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		v_card.push_back(input);
	}

	dfs(0, 0);
	cout << answer;

	return 0;
}

💻 문제 풀이 : Python

Combination 라이브러리사용

import sys
from itertools import combinations

N, M = map(int, input().split())
cards = list(map(int, input().split()))
answer = 0

combi_cards = list(combinations(cards, 3))

for card in combi_cards:
    card_sum = sum(card)
    # for i in range(3):
    #     card_sum += card[i]
    if(card_sum > M):
        card_sum = 0
    answer = max(card_sum, answer)

print(answer)

Backtracking 사용

import sys

def dfs(depth, start):
    if depth == 3:
        # print(selected)
        card_sum = sum(selected)
        if card_sum <= M:
            answer.append(card_sum)
        return
    for i in range(start, N):
        if visited[i] == 1:
            continue
        visited[i] = 1
        selected.append(cards[i])
        dfs(depth + 1, i + 1)
        visited[i] = 0
        selected.pop()

N, M = map(int, input().split())
cards = list(map(int, input().split()))

visited = [0] * N
selected, answer = [], []
dfs(0,0)
print(max(answer))

---

📌 memo 😊

---

Ref)
https://velog.io/@kimdukbae/BOJ-10819-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%B5%9C%EB%8C%80%EB%A1%9C-Python