[BOJ / c++] 2798번 - 블랙잭

링크

https://www.acmicpc.net/problem/2798

풀이

N개의 카드중 3개를 뽑아 더하여 구하는 조합 문제이다. 이번에 배운 next_permutation을 이용한 조합알고리즘을 사용해보았다.

3중첩 for문, next_permutation, dfs를 이용하여 구현하였으며 이중 for문의 성능이 가장 우수하였고 dfs는 시간초과로 인하여 틀렸다.

코드

for문을 이용한 코드

#include<iostream>

using namespace std;


int main() {

	int n,m;
	int card[100];

	cin >> n>>m;
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				int sum = card[i] + card[j] + card[k];
				if (sum <= m && sum > result) {
					result = sum;
				}
			}
		}
	}
	cout << result;

}

next_permutation을 이용한 코드

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

using namespace std;




int main() {

	int n,m;
	int card[100];

	cin >> n>>m;
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}

	vector<int> com;
	for (int i = 0; i < n - 3; i++) com.push_back(0);
	for (int i = 0; i < 3; i++) com.push_back(1);

	int result = 0;
	do {
		int sum = 0;
		for (int i = 0; i < n; i++) {
			if (com[i]==1) {
				sum += card[i];
				if (sum > m)break;
			}
		}

		if (sum <= m && sum > result) {
			result = sum;
		}

	} while (next_permutation(com.begin(), com.end()));

	cout << result;

}

dfs를 이용한 코드

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

using namespace std;


int n, m;
int card[100];
vector<int> com;
int sum = 0;
int result=0;

void dfs(int depth, int next) {
	if (depth == 3&& result<sum) {
		result = sum;
		return;
	}

	for (int i = next; i < n; i++) {
		
		
			sum+=card[i];

			if(sum<=m)dfs(depth + 1, i+1);

			sum -= card[i];
	}
}

int main() {


	cin >> n>>m;
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	dfs(0, 0);
	cout << result;
}

아래에서 위순서로 for문, dfs, next_permutation 실행결과