[백준/BOJ] 2798번 블랙잭 (C/C++)

백준 온라인 저지(BOJ) 2798번 블랙잭
https://www.acmicpc.net/problem/2798

2798번: 블랙잭

* 사용언어 : C언어, C++

 

1. 문제

N 장의 카드 중 3장을 합했을 때
M 을 넘지 않으면서 M 과 최대한 가까운 카드 3장의 합을 출력

 

2. 풀이

브루트 포스 알고리즘로 분류된 문제인 만큼
단순하게 설계해서(중첩 반복문) 쉽게 풀면 됩니다.

N 장 중 3장을 고르는 모든 경우의 수를 고려해야 하므로,
3중 for 문을 구현하여 3장의 합을 찾고 max 와 비교하는 방식으로 구현했습니다.

시간 복잡도를 좌우하는 N 의 크기는 max 가 100 이므로
N^3 을 해도 1,000,000(백만)이라 문제가 되지 않습니다.


추가로
3중 for 문을 특별한 조건 없이 사용하면 이미 고른 카드를 다시 고를 수 있게 됩니다.

이러한 현상을 막기 위해 3개의 index 가 모두 다른 경우만
sum 을 확인하도록 if 문과 continue 를 추가했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2798_블랙잭
1112KB	0ms
*/
#include <cstdio>

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, a[100];
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%d ", &a[i]);
	
	int sum, max = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			for (int k = 0; k < n; ++k) {
				if (k == i || k == j) continue;
				sum = a[i] + a[j] + a[k];
				if (sum > max && sum <= m) max = sum;
			}
		}
	}

	printf("%d\n", max);
	return 0;
}