[BOJ] 백준 2798 블랙잭

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

 Input 

5 21

5 6 7 8 9

 

 Output 

21 

▶ 6 + 7 + 8 = 21

 

N이 크지 않은 숫자이므로 NC3으로 모든 경우의 수에 대한 최적의 해를 구합니다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M;
int result;
vector<int> v;
 
// 조합
void DFS(int idx, int cnt, int sum){
 
        // 3장의 카드 선택되어, 합이 M이하인 경우
        if (cnt == 3 && sum <= M){
            result = result < sum ? sum : result;
            return;
        }
 
        // 선택할 카드가 없거나 
        if (idx >= N || cnt > 3 || sum > M)
                 return;
 
        // 해당 카드 선택한 경우
        DFS(idx + 1, cnt + 1, sum + v[idx]);
        // 해당 카드 선택하지 않은 경우
        DFS(idx + 1, cnt, sum);
}
 
int main(void){
 
        cin >> N >> M;
        v.resize(N);
 
        for (int i = 0; i < N; i++){
             cin >> v[i];
        }
            
        DFS(0, 0, 0);
 
        cout << result << endl;
}