[백준] 2798번 - 블랙잭 (C++/파이썬) 문제 및 풀이

문제) 백준 - 브루트 포스(Brute Force) - 블랙잭

-> www.acmicpc.net/problem/2798

2798번: 블랙잭

 

카드를 세 장 뽑으므로, 삼중 반복문을 이용하여 카드 세 장을 선택하며 그 카드들의 합을 계산하여 확인한다.

 

 

c++ 소스코드)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, sum = 0;
vector <int> card;
int main() {
	//빠른 입출력
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		int temp; cin >> temp;
		card.push_back(temp);
	}

	//카드 세 장 선택
	for (int i = 0; i < n - 2; ++i)
		for(int j = i + 1; j < n - 1; ++j)
			for (int k = j + 1; k < n; ++k) {

				//카드의 합이 m을 초과할 경우 무시
				if (card[i] + card[j] + card[k] > m)
					continue;

				//m에 가장 가까운 수 선택
				else
					sum = max(sum, card[i] + card[j] + card[k]);

			}
	
	cout << sum << "\n";

	return 0;
}

 

 

 

Python 소스코드)

import sys
#빠른 입출력
input = sys.stdin.readline

N, M = map(int, sys.stdin.readline().split())

card = list(map(int, sys.stdin.readline().split()))

answer = 0

#카드 세 장 선택
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
        	
            #카드의 합이 m을 초과할 경우 무시
            if card[i] + card[j] + card[k] > M:
                continue
            
            #m에 가까운 수 선택
            else:
                answer = max(answer, card[i] + card[j] + card[k])
                
print(answer)

 

 

※ 재귀 호출을 이용한 완전 탐색

 

2798번 문제를 해결하기 위해, 카드 세 장을 뽑는 과정에서 삼중 반복문을 이용하였다. 만약, 세 장 초과의 카드를 뽑을 때는 그럼 어떻게 해야 할까? 초과되는 카드 수만큼 반복문을 중첩해야 되기 때문에 시간 복잡도 측면에서 비효율적이다. 즉, 위의 코드는 범용성 측면에서 비효율적인 것을 알 수 있다. 그래서 세 장 초과인 경우를 생각해 재귀 호출을 이용하여 무식하게(Brute Force) 풀어봤다. 

 

재귀 호출을 이용한 C++ 소스코드)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void cardsum(int idx, int cnt, int sum);
int n, m, res = 0;
vector<int> card;


int main() {
	//빠른 입출력
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		int temp; cin >> temp;
		card.push_back(temp);
	}

	cardsum(0, 0, 0);

	cout << res << "\n";
	return 0;
}

void cardsum(int idx, int cnt, int sum) {

	//기저 사례 1: 카드 3장을 뽑고  합이 m 이하인 경우 성공
	if (cnt == 3 && sum <= m) {
		res = max(res, sum);
		return;
	}

	//기저 사례 2: 인덱스가 벗어나거나 카드를 3개 초과해서 고르거나 합이 넘을 경우 실패
	if (idx >= n || cnt > 3 || sum > m) return;


	cardsum(idx + 1, cnt + 1, sum + card[idx]);
	cardsum(idx + 1, cnt, sum);
}