728x90
블랙잭
100가지 중에 3가지를 고르는 경우의 수는, 10C3 = 161,700
경우의 수 별로 없으면 컴퓨터의 무식하고 빠른 연산을 살려서 모든 경우를 체크하여 보자.
가능한 조합을 모두 고르는 함수를 마침 공부하였다!
sum <= m 조건에서 정답을 찾는다.
즉, m - sum >= 0 인 상황에서
m - sum < ans - sum 이면, ans = sum으로 한다.
#include <cstdio>
#include <vector>
using namespace std;
int a[100];
int n, m;
int min_dif {987654321};
int ans;
void combination(vector<int> v, int r, int idx){
if (r == 3) {
int sum = v[0] + v[1] + v[2];
int dif = m - sum;
if (dif >= 0 && dif < min_dif ) {
min_dif = dif;
ans = sum;
}
return;
}
int next = v.empty() ? 0 : idx + 1;
for (int i = next; i < n; ++i){
v.emplace_back(a[i]);
combination(v, r + 1, i);
v.pop_back();
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i=0; i<n; i++){
scanf("%d", &a[i]);
}
vector<int> v;
combination(v, 0, 0);
printf("%d\n", ans);
return 0;
}
728x90
'알고리즘, 자료구조 > 알고리즘' 카테고리의 다른 글
1018 체스판 다시 칠하기 (0) | 2019.07.18 |
---|---|
[brute-force] 1436 영화감독 숌 (0) | 2019.07.16 |
17298 오큰수 (4) | 2019.07.14 |
Greedy 알고리즘 (2) | 2019.07.14 |
1966 프린터 큐 (589) | 2019.07.01 |
댓글