본문 바로가기
알고리즘, 자료구조/알고리즘

[brute-force] 2798 블랙잭

by Wordbe 2019. 7. 15.
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

댓글