[BOJ] 2798 블랙잭

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

2798번: 블랙잭

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

조합(combination)

 

---------------------------------------------------풀이----------------------------------------------------

 

카드 중 세 개를 고르는 조합 문제.

선택한 개수가 3개 이상이거나 sum이 M보다 크면 return.

중복되지 않도록 앞에서부터 선택한 인덱스의 최댓값 이후부터 선택한다. 즉, cur부터 선택한다.

예를 들어, 이전에 3을 선택했으면 4~n까지 중에서 하나를 고르도록 한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int N, M, answer = 0;
int cards[100];
int visited[100] = {false, };

// 선택된 개수 selected, 현재 선택할 수 있는 카드의 인덱스 중 가장 작은 값 cur, 현재 합 sum
void combi(int selected, int cur, int sum){
    if(sum > M){
        return;
    }
    if(selected >= 3){
        if(sum <= M && sum > answer){
            answer = sum;
        }
        return;
    }
    for(int i = cur; i < N; i++){
        visited[i] = true;
        combi(selected+1, i+1, sum+cards[i]);
        visited[i] = false;
    }
}

// 3장을 골라 M과 가장 가까운 M 이하의 수 만들기
int main(void){
    FASTIO;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> cards[i];
    }
    combi(0,0,0);
    cout << answer << "\n";
    return 0;
}

---------------------------------------------------후기----------------------------------------------------

 

간단한 조합 문제. 모든 가능한 케이스를 탐색하는 brute force.