[백준 2798] 블랙잭

전형적인 DFS 사용한 조합론 문제이다.

 

DFS 돌때 자신의 뒤 idx부터 호출하게 하고

총 3개이면 조건판단해서 종료되게 하였다.

 

시간초과를 방지하기 위해

3개를 조합하는 과정에서 M을 이미 넘어가게 되면 스킵하게 하였다

 

---

#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 101

using namespace std;

int N, M;
vector<int> arr;
int ans = 0;

void solve(int idx, int sum, int cnt){
    // 종료조건이면 확인하고 return
    if(cnt == 3){
        // 최신화가 안되어있었거나 지금꺼가 M에 더 가까우면 최신화
        if (M - ans > M - sum)
        {
            ans = sum;
        }
        return;
    }

    for (int i = idx + 1; i < N; i++){
        // M 보다 커지면 skip
        if(sum + arr[i] > M) continue;

        solve(i, sum + arr[i], cnt + 1);

        if(ans == M) return;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    int x;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    solve(-1, 0, 0);

    cout << ans;

    return 0;
}